Adding NTFS Write Functionality to OSX

Okay the story is like this: I have Windows, Ubuntu and MacOSX systems in my home and office and sometimes I backup or transfer files using a 8GB USB thumb drive (another way is to use Dropbox). This works perfectly fine until one day I met a 4.x GB file and OOPS! FAT32 filesystem does not allow a single file with that size! As a result, I tried to search for a mulit-platform supported filesystem which also supports large files. I tried NTFS. It works fine with Windows and Ubuntu but it can only be read from MacOSX, without write... When I was going to give up, a friend suggested this Lifehacker article to me (thanks again to my friend!). According to that article, I added NTFS write function to the MacOSX system and now my problem is solved~

The steps are simple:

1. Download and install MacFUSE from here
2. Download and install NTFS-3G for Mac OSX from here
3. Restart your Mac
4. Enjoy~

Using Thread in iOS

iOS SDK has its own NSThread (class reference here) class to handle thread operations, and using it is pretty simple:

In the above source, func_to_call is the function to be performed in the thread and parm_to_func (can be nil) is the parameter to be passed to func_to_call. If one would like to call functions in the main thread from child thread (probably you want to do this when the child thread is going to end and notifying the main thread is required), using the following:

In this line, func_in_main is the function to be called in main thread.

Note: The above method should be compatible with iOS 3.x.

Macbook Pro cannot boot up with continuous beep and black screen

Today my colleague told me that his 13" macbook pro (2009 ver.) cannot boot up with black screen. After taking a look, I found that it even gives out crazily annoying beep sound continuously (beep-beep-beep, halt, beep-beep-beep, halt, ......). I have not met that before and turned to Google for help. After some looking and trying (at some time I thought it is because a disc stuck in the drive), finally I found a few sources all point out that the 3-beep sound means "bad memory". The colleague then tried taking the two 1-GB RAM in and out to test and BINGO! The problem was caused by one single faulty RAM! So I will know what to do if any of my machine gives me that sound......

Update: One of my friends told me just now those beep sounds are called "beep code" and their meanings are dependent to different BIOS. A reference of Mac machines can be found here.
Update: Another reference in Wikipedia.

Notes of differences between x86 and x64 on programming

Notes: For reference only, actual situation should be affected by CPU type, kernel, compiler, etc.

Data Type	Ubuntu x86	Ubuntu x64	Win32	MacOS 10.6	SunOS 5.10	MIPS	iOS
char	1	1	1	1	1	1	1
short	2	2	2	2	2	2	2
int	4	4	4	4	4	4	4
long	4	8	4	8	4	4	4
long int	4	8	4	8	4	4	4
long long	8	8	8	8	8	8	8
float	4	4	4	4	4	4	4
double	8	8	8	8	8	8	8
long double	12	16	8	16	16	8	8
pointer	4	8	4	8	4	4	4

Mathematical Prove (3)

Bilinear Pairing over Composite Group

Given groups $\mathbb{G}$ and $\mathbb{G}_T$ of order $N=pq$ where $p,q$ are prime, and a bilinear pairing $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$.

The subgroups of $\mathbb{G}$ with size $p,q$ are defined as $\mathbb{G}_p$ and $\mathbb{G}_q$. Let generator of $\mathbb{G}$ be $g$. The generators of $\mathbb{G}_p$ and $\mathbb{G}_q$ be $g_p$ and $g_q$ can be computed as $g_p = g^q \in \mathbb{G}_p$ and $g_q = g^p \in \mathbb{G}_q$

In addition to basic bilinear pairing properties, bilinear pairing over composite group holds some additional properties:

• $e(g_p,g_q) = e(g^q,g^p) = e(g,g)^{pq} = e(g,g)^N = 1$
• $e({g_p}^a{g_q}^b,{g_p}^c) = e(g^{qa+pb}, g^{qc}) = e(g,g)^{q^2ac+Nbc} = e({g_p}^a,{g_p}^c)$

Attribute-based Broadcast Encryption

Attribute-based Broadcast Encryption (ABBE) makes use of Attribute-based Encryption scheme to implement broadcast encryption. In attribute-based encryption, a ciphertext is bundled with a data access policy (policy for short) which consists of a list of attributes connected by logic gates (typically AND and OR). Each user in the system possesses a list of attributes. To determine if a user is a legitimate decryptor of the ciphertext, the system compares his attributes with the policy. If the policy is satisfied, the user is able to decrypt the ciphertext.

Compared with conventional broadcast encryption, attribute-based encryption is like separating users into different groups and the access control (using policy) is enforced by manipulating access controls in those groups. If the number of attributes is much less than the total number of users in the system, ABBE has a big advantage on efficiency. However, it cannot enforce ad-hoc access control on every individual user like conventional broadcast encryption.

Hence, some proposed using each bit of user ID as attribute, which makes the total number of attributes becomes log N (assuming N users). This number is much smaller than the total number of users and it sounds promising. However, during my study I found two major problems in this scheme when the number of legitimate users grows large.

First, in order to get a small ciphertext size, the scheme uses Boolean algebra simplification algorithm. The idea is to first list all user IDs of legitimate users in a truth table, then applies the simplification algorithm to get a shorter Boolean algebra expression without altering its result, and this problem is NP-Hard. The two most famous algorithms for this task are Quine-McCluskey algorithm and Espresso heuristic logic minimizer. The complexity of them is yet to be found, but according to my preliminary testing, the running time (for just Boolean algebra simplification) can be much longer than running encryption of Boneh's broadcast encryption. A better simplification algorithm or a better implementation of it is required.

Second, the number of sum-of-product terms output from the simplification is not a constant. In other words, the ciphertext of this scheme will have a variable size. And this leads to a question: How large can the size be? I found it difficult searching for or understanding literature which discusses about this problem. Therefore, I try to run my own test again. I tried to compute both average case and worst case on small N (since I have to generate all combinations, it is already very large even for small N, e.g. 32). From my test, the growth of average size seems to be O(log N). For worst case, however, the size seems to be N/2. In my opinion, the problem is how often the size stays at O(log N). In real application, I think a good average bound is not enough, a good worst case bound is needed. Imagine when N = 10M, N/2 will be 5M and it results in a enormous ciphertext size.

日本語文法(4)

尊敬語 (特別形):

言う	おっしゃる (おっしゃいます)
いる/行く/来る	いらっしゃる (いらっしゃいます)
くれる	くださる (くださいます)
知っている	ごぞんじだ
する	なさる (なさいます)
食べる/飲む	召し上がる
見る	ご覧になる
寝る	おやすみになる
死ぬ	お亡くなりになる
だ/ている/て行く/て来る	ていらっしゃる
てくれる	てくださる
着る	お召しになる

謙讓語 (特別形):

あげる	さしあげる
もらう	いただく
言う	申し上げる
聞く (ask)	伺う
行く (尋ねる/訪問する)	伺う
見る	拝見する
見せる	お目に掛ける
会う	お目に掛かる
知っている	存じあげている
てあげる	て差し上げる
てもらう	ていただく

丁重語 (特別形):

言う	申す
行く/来る	参る
いる	おりる
する	いたす
食べる/飲む	いただく
て行く/て来る	て参る
ている	ておりる
思う	存じる
知っている	存じている
ある	ござる (ございます)
だ	でござる (でございます)

Completely Dim an iMac Monitor

For unknown reason, Apple does not allow an iMac Monitor to go completely black via the brightness control. Furthermore, the energy saver setting does not allow an interval less than 1 min. These can be annoying that the monitor keeps switching on while some others are VNC+ing the machine. Although there is no official "solution" from Apple, there is some free utility programs which can do the job. For example, this can turn the iMac screen completely black and can be recovered with a hotkey combination.

HyperTerminal for Windows Vista/7

HyperTerminal is not included in Windows Vista/7. If you want to use it, you will need two files: hypertrm.exe and hypertrm.dll

To obtain these two files, you may either Googling it online or if you have a Windows XP machine, you may find them in the following paths:

• C:\Program Files\Windows NT\hypertrm.exe
• C:\Windows\system32\hypertrm.dll

Copy both files to your Windows Vista/7 machine and remember to put them into the same directory.

Connecting to HTTPS with Untrusted Certificate from iPhone OS

By default one can use NSURLRequest and NSURLConnection to connect to a HTTP/HTTPS server. However, the iPhone OS may block the connection if the HTTPS server does not have a trusted certificate (e.g. a self-signed certificate is considered untrusted). After some Googling, here is one of the solutions: Adding the following two functions to the NSURLConnection delegate.

Windows Azure SDK Requirements

• Windows Vista / Windows 7 / Windows Server 2008 / Windows Server 2008 R2
• IIS 7.0 (with ASP.NET, WCF HTTP Activation, Static Content, and optionally CGI)
• Microsoft Visual Studio 2010/ Microsoft Visual Web Developer 2010 Express / Microsoft Visual Studio 2008 SP1 / Microsoft Visual Web Developer 2008 Express Edition with SP1.
• SQL Server 2005 Express Edition or above

Access Java Class Variables from NDK

Access Java class variables from NDK (non-static function) in C:

• env and obj are the first two parameters of the NDK function
• "Ljava/lang/String;" is called the field descriptor of type String

Field Descriptor of other Variable Types:

• Remember the semi-colon
• Replace "Get" by "Set" for Set Field Functions

Field Descriptor	Type	Get Field Function
Z	boolean	GetBooleanField
B	byte	GetByteField
C	char	GetCharField
S	short	GetShortField
I	int	GetIntField
J	long	GetLongField
F	float	GetFloatField
D	double	GetDoubleField
Ljava/lang/String;	String	GetObjectField
[I	int[]	GetObjectField, and then cast it to an array jintArray *arr = reinterpret_cast<jintArray*>(&data);
[Ljava/lang/Object;	object[]	GetObjectField, and then cast it to an array

OSX C/C++ Header Differences with Linux

• Header <mntent.h> does not exist
• Header <linux/rtc.h> does not exist
• Header <sys/sysinfo.h> does not exist
• In <string.h>, function strndup() does not exist
• In <unistd.h>, function ftruncate64() does not exist
• In <netinet/in.h>, struct ip_mreqn does not exist
• Struct statfs requires <sys/param.h> and <sys/mount.h>
• Variable environ doest not exists, but you can "access" it using function _NSGetEnviron() defined in <crt_externs.h>
• To retrieve full path of current executable, use function _NSGetExecutablePath() defined in <mach-o/dyld.h>

Android NDK Differences with Linux

• C++ STL is not included Update: stlport is included since revision 5
• In <mntent.h>, function setmntent() does not exist
• In <dirent.h>, functions seekdir(), telldir() does not exist
• Macro INET_ADDRSTRLEN is not defined in <netinet/in.h> Update: added since revision 5b
• Macro PTHREAD_EXPLICIT_SCHED is not defined in <pthread.h>
• Marcos WEXITSTATUS, WTERMSIG, WIFSIGNALED, etc are only defined in <sys/wait.h>  (One can also find them in <stdlib.h>  for Linux)
• Although function ftruncate64() is included in header <unistd.h>, it is not included in the prebuilt libraries. Hence it causes linking error while this function is used
• Although you can include <sys/sysinfo.h>, struct sysinfo does not exist (it is disabled in the header file). If you have to use it, try this way.

Android NDK Development

Some remarks I would like to make while developing on Android NDK:

• Package, class and function names in Java are specified by function name in C/C++
• For all JNI wrapper functions, remember to add JNIEnv *env and jobject object to the front of the parameter list. They represent the environment pointer and the Java class object which calls this function.
• Parameters are passed into wrapper functions by value. To the best of my knowledge, there is no way to pass in parameters by reference.
• If the wrapper source is in cpp, remember to include all function prototypes in
  
• Include all source files in subdirectory src: LOCAL_SRC_FILES := $(addprefix src/,$(notdir $(wildcard $(LOCAL_PATH)/src/*.cpp $(LOCAL_PATH)/src/*.c)))
• Make use of include $(call all-subdir-makefiles) to make a recursive building hierarchy
• While using variable LOCAL_STATIC_LIBRARIES, try putting the highest level libraries in the front to prevent linking error
• In order tot check the output of stdout and stderr, you have to set by using adb (included in Android SDK), and then you can view them using ./adb logcat
  ./adb shell stop
  ./adb shell setprop log.redirect-stdio true
  ./adb shell start
  Update: Stopping and starting the shell may cause the whole emulator hangs now. To redirect stdout/stderr, add "log.redirect-stdio=true" to /data/local.prop on the device (create one if the file does not exist) and restart the device
• STL library is not included in NDK. If you need to use STL library in your NDK code, you have to use stlport
• DO NOT create thread inside NDK
• Directory /tmp DOES NOT exist in Android. I have tried to search for it for hours without any luck. According to what I found, applications should manage their own files (temp or non-temp) within the local filesystem sandbox on their own
• There is a script to let you build a NDK toolchain since NDK revision 5
• Linking with "-lpthread" is not required, including that will cause error

日本語文法(3)

轉形:

可能 表示有此能力 表示/評價目標的被動作的可能性, 性質, 機能 飲む => 飲める 食べる => 食べられる する => できる 来る => こられる

受身 被動式 因對方對主語/主語的物件做了此動作而受到了傷害 表示一般/眾所周知的事實, 強調事情本身而非做此動作的人 飲む => 飲まれる 食べる => 食べられる する => される 来る => こられる

使役 放任 強制 許容 誘發 (令到對方有某種感受, 無上下限制) 飲む => 飲ませる 食べる => 食べさせる する => させる 来る => こさせる

使役受身 飲む => 飲ませられる / 飲まされる 食べる => 食べさせられる する => させられる 来る => こさせられる

意志 飲む => 飲もう 食べる => 食べよう する => しよう 来る => こよう

日本語文法(2)

網上找到有關副詞的用法, 未知有沒有謬誤, 僅供參考

必須接「～ている」	いま ただいま
必須接「～た」	とうとう ついに かねて すでに もう さすがに やっと
必須接「肯定敘述」	必ず きっと ぜひ
必須接「否定(～ない)」	必ずしも どうしても どうも めったに べつに すこしも まさか 一向 ちょとも ぜんぜん 全く
必須接「疑問、反問(～か)」、「感動」(～でしょう/か)	どうして なぜ なんと いつ いかが
必須接「(～下さい)」	どうぞ どうか
必須接「猜測、推量(～でしょう/と思う)」	おそらく たぶん さぞ
必須接「假定(～たら/～ば)」	もしかして ひょっとして もし まんいち かりに
必須接「比喻、舉例(～ようだ/みたい)」	まるで あたかも ちょうど どうやら
必須接「～ても」	たとえ せめて いくら
必須接「～なければならない」	どうしても 必ず ぜひ
必須接「～だけ」	だた 僅かに

日本語文法

V+なければならない	表示"一定要怎樣怎樣做"的意思
N+がする	表示感覺到 (e.g. 風がする)
V+て、V+て、V	表示動作次序
V+たり、V+たり、V	表示做過什麼 (未必包括所有做過的動作)
V+ている	現在進行式 (Present Imperfect)
Vt+ている	表示狀態
Vi+てある	表示狀態
V+てしまう	表示:  動作完成 (Perfect Tense?) 表示可惜/悔意 表示驚訝, 意外地發生
V+ておく	表示:  預先做好(動作) 表示動作暫時性
V+てほしい	表示希望別人做(動作)
ので	表示因果
N/A/V + ようだ	用法:  接近判斷 / 婉轉語氣 修飾名詞: ~ ような+N 修飾形容詞/動詞 (~adverb): ~ ように+A/V 比喻? 飲む => 飲むようだ 食べる => 食べるようだ 早い => 早いようだ 綺麗な => 綺麗なようだ 学生 => 学生のようだ
N/A/V + みたい	接近判斷 / 婉轉語氣  飲む => 飲むみたい 食べる => 食べるみたい 早い => 早いみたい 綺麗な => 綺麗みたい 学生 => 学生みたい
V/A + そうだ	樣態 形容詞 - 表示由對像的外觀所得出的樣子/性質之推論 動詞 -  表示預想將會發生的狀況 根據觀察對事物的狀況/樣子作出推測 對名詞/動詞作出修飾: そうなN, そうにV 飲む => 飲みそうだ 飲まない => 飲みそうもない 食べる => 食べそうだ 食べない => 食べそうもない いい => よさそうだ 早い => 早そうだ 早くない => 早くなさそうだ 綺麗な => 綺麗そうだ 綺麗ではない => 綺麗ではなさそうだ
N/V/A + そうだ	傳聞 表達讀到/聽到的情報(report, without personal feeling/estimation?)  飲む => 飲むそうだ 飲まない => 飲まないそうだ 食べる => 食べるそうだ 食べない => 食べないそうだ 早い => 早いそうだ 早くない => 早くないそうだ 綺麗な => 綺麗だそうだ 綺麗ではない => 綺麗ではないそうだ 学生 => 学生だそうだ 学生ではない => 学生ではないそうだ
N[に]/Aな[に]/Aい[く]+なる	自然變化 (人為變化用 ~する) 強調變化結果  早い => 早くなる 綺麗な => 綺麗になる 学生 => 学生になる
N[に]/Aな[に]/Aい[く]+する	表示:  人為變化 (自然變化用 ~なる) 決定 強調變化結果 早い => 早くする 綺麗な => 綺麗にする 学生 => 学生にする
~ことにする	用法:  表示是由自己意志決定的事 表達習慣 (ことにしっている)
~ことになる	用法:  強調已經決定的結果 (忽略做決定的責任) 表示預定會做的事情/一般規則 (ことになっている)
A/V(ます)+すぎる	太過 (too~) 複合動詞?  飲む => 飲みすぎる 食べる => 食べすぎる 早い => 早すぎる 綺麗な => 綺麗すぎる
のに	表示:  逆接 (表示婉惜) 表示用途 (名詞化+に?)
V+なおす	重新做(動作) 複合動詞?  飲む => 飲みなおす 食べる => 食べなおす
V+にくい	表示困難(意志動詞), 低可能性(無意志動詞)  飲む => 飲みにくい 食べる => 食べにくい
V+やすい	表示容易(意志動詞), 高可能性(無意志動詞)  飲む => 飲みやすい 食べる => 食べやすい
V+たばかりだ	(狀態上)心理上剛剛發生/完成  飲む => 飲んだばかりだ 食べる => 食べたばかりだ
V+つもりだ	表示將來的預定/計劃  飲む => 飲むつもりだ 食べる => 食べるつもりだ
V+つもりはない	表示沒有這個意願  飲む => 飲むつもりはない 食べる => 食べるつもりはない
Nの/V+予定だ	預定/計劃, 比つもり更肯定  飲む => 飲む予定だ 食べる => 食べる予定だ 木曜日 => 木曜日の予定だ
N/A/V+らしい	推算, 推論 (基於某些事情或東西), 並不確定, 有"估計"的意思  飲む => 飲むらしい 食べる => 食べるらしい 早い => 早いらしい 綺麗な => 綺麗らしい 学生 => 学生らしい
N/A/V+かもしれない	表示有這個可能性  飲む => 飲むかもしれない 食べる => 食べるかもしれない 早い => 早いかもしれない 綺麗な => 綺麗かもしれない 学生 => 学生かもしれません
たら	用法:  前句不能是過去式 表示假定條件 表示(將會發生但未發生?)事情發生後會發生/做的事 表示(已發生?)事情的驚訝/發現, 用以報告已發生的事情 表示一次性事情, 不能用作表達恆常發生的事情/法則 可用作表示警告 (此用法與 たら 相通) 前句為名詞時與 なら 相通 飲む => 飲んだら 食べる => 食べたら 早い => 早かったら 綺麗な => 綺麗だったら 学生 => 学生だったら
と	用法:  前句不能是過去式 前句為固定條件, 一般不能是問題 不能表示意志表現, 除非是明顯習慣 表示非常高的發生機率 可表示一般事實/習慣/程序/警告 後面可以接過去式, 表達過去已發生的事情 後面不能接 ください 飲む => 飲むと 食べる => 食べると 早い => 早いと 綺麗な => 綺麗だと 学生 => 学生だと
ば	用法:  前/後句都不能是過去式 前句多為不定的情況(e.g.問題) 前句可為非肯定情況/疑問/非事實 表示"如果"的味道較重 暗示如果違反了前句的情況, 會有其他安排/事/etc 後面不能出現意志表現(e.g. 命令, ください), 除非前句為形容詞(い/な)/できる/ある 不會出現前句是好事但後句為壞事 表示提議/意見? 後面不會出現問句 不會用作表達過去發生的事情 可用作表示恆常的事情/法則, 即非一次性的事情 飲む => 飲めば 食べる => 食べれば 早い => 早ければ 綺麗な => 綺麗なら(ば) 学生 => 学生なら(ば)
~ば~ほど~	表示: 越~越~ (e.g. 近ければ近いほど便利だ = 越近越方便)
なら	表示講者從對方談話中知道事情/狀況後, 所表達的提議/意志/感覺/意見/拜託之類的東西  可以出現提議 不會出現警告 飲む => 飲むなら 食べる => 食べるなら 早い => 早いなら 綺麗な => 綺麗なら 学生 => 学生なら
N+にとって	對於所談論的事物, 就著N的主場/感覺給予評價。N多為人或組織 (個人感覺像active reference)
N+に対して	表示動作, 感情, 態度的目標對象 (個人感覺像passive reference)
V1+ように+V2	為了V1而做V2  V1為無意志動詞 V1為任何動詞的否定形(ない) V1為可能形/可能表現 前後主語可以不同
V1/Nの+ために+V2	為了V1/N而做V2  V1為意志動詞 前後主語必定相同
V/A/N+はずだ	用法:  應該/Should be, 基於客觀理由所作的推測 表示「當然」的事實/情況 表示「沒有可能」(はずがない) 表示預想以外的結果, 帶有驚訝/可惜的心情 (はずではなかった) 飲む => 飲むはずだ 食べる => 食べるはずだ 早い => 早いはずだ 綺麗な => 綺麗なはずだ 学生 => 学生のはずだ
V+ことがある	用法:  表示偶然/非定期重複發生的事情 (V為非過去式) 表示經驗 (V為過去式) 飲む => 飲むことがある 食べる => 食べることがある 飲む => 飲んだことがある 食べる => 食べたことがある
V+ていく	用法:  先做V, 然後移動 V是移動的手段/方法 V是移動的狀態 當V是移動動詞時, 對主語來說, 表達V的動作方向 表達V的動作的時間性方向 (from past/to future) 表達V的動作的持續 (past/future)
V+てくる	用法:  先做V, 然後移動 V是移動的手段/方法 V是移動的狀態 當V是移動動詞時, 對主語來說, 表達V的動作方向 表達V的動作的時間性方向 (from past/to future) 表達V的動作的持續 (past/future) 表示去做一做V然後就回來 表示動作/感覺的接近 表示變化的出現/開始
N+とする	用法:  N1作為N2... (N1はN2として...) S把N2作為/當作N1... (SはN1としてN2を...)
V[よう]+とする	用法:  V為意志形 (e.g. 行こう) 表示為了實行V而去努力並嘗試 表示第三者 (不是自己) 並無這個意願 (V[よう]+としない) 表示正要做V / 想做但未完成V (V[よう]+とした) 表示自然現象/無意志的事物發生變化之前
N1 は N2 [と/に] 比べて XXX が	N1和N2在XXX方面相比

Mathematical Prove (2)

Prove $e(A,X+Y) = e(A,X) \cdot e(A,Y)$ where $e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$ is a bilinear pairing and $A,X,Y \in \mathbb{G}$

Since $X,Y \in \mathbb{G}$, assume $X = xP, Y = yP $ where $ P $ is a generator of $\mathbb{G}, x,y \in \mathbb{Z}_p$ where $p$ is the order of $\mathbb{G}$
$e(A,X+Y) = e(A,xP+yP) = e(A,P)^{x+y} = e(A,P)^x \cdot e(A,P)^y$
$= e(A,xP) \cdot e(A,yP) = e(A,X) \cdot e(A,Y)$

Mathematical Prove (1)

Prove $(1-x)^{x^{-1}N} < e^{-N}$ for $x \in (0,1)$

Assume $(1-x)^{x^{-1}N} < e^{-N}$, then
$ln((1-x)^{x^{-1}N}) < -N$
$x^{-1}Nln(1-x) < -N$
$x^{-1} ln(1-x) < -1$
$ln(1-x) < -x$
$ln(1-x) + x < 0$

So we can prove $ln(1-x) + x < 0$ instead
Let $f(x) = ln(1-x) + x$,
$f'(x) = \frac{d}{d(1-x)}ln(1-x)\cdot\frac{d}{dx}(1-x)+\frac{dx}{dx} = -\frac{1}{1-x} + 1$

Since $f'(x) < 0$ for $x \in (0,1)$ and $f'(x) = 0$ when $x = 0$, $f(x)$ is strictly decreasing for $x \in (0,1)$ with the greatest value $f(0) = ln(1-0) + 0 = 0$. Therefore, $f(x) < 0$ for $x \in (0,1)$ and so $(1-x)^{x^{-1}N} < e^{-N}$ for $x \in (0,1)$

The Legendre Symbol

Introduction:

The Legendre Symbol tells us that whether a number $x \in \mathbf{Z}^*_p$ where p is prime is a perfect square (also called quadratic residue).

Definition:

For a prime p and $x \in \mathbf{Z}^*_p$, the Legendre Symbol $\mathbf{J}_p(x)$ is defined as:
$\mathbf{J}_p(x) = \begin{cases} 1 & \mbox{if } x\mbox{ is a perfect square in }\mathbf{Z}^*_p \\ 0 & \mbox{if }gcd(x,p) \neq 1 \\ -1 & \mbox{if } x\mbox{ is not a perfect square in }\mathbf{Z}^*_p \end{cases}$
The Legendre Symbol is computed by $\mathbf{J}_p(x) \equiv x^{\frac{p-1}{2}} \mbox{ mod } p$

Discussion and Proof:

• Since p is prime, $x = kp$ where $k \in \mathbb{Z}$ if $gcd(x,p) \neq 1$. As a result, $\mathbf{J}_p(x) = (kp)^{\frac{p-1}{2}} = 0 \mbox{ mod } p$
• If x is a perfect square in $\mathbf{Z}^*_p$ and g is a generator of $\mathbf{Z}^*_p$, x can be written as $g^{2i} \mbox{ mod } p \mbox{ where } 1 \leq 2i \leq p-1$. As a result, $\mathbf{J}_p(x) = g^{\frac{2i(p-1)}{2}} = g^{i(p-1)} = 1 \mbox{ mod }p$
• If x is not a perfect square in $\mathbf{Z}^*_p$ and g is a generator of $\mathbf{Z}^*_p$, x can be written as $g^{i} \mbox{ mod } p \mbox{ where } 1 \leq i \leq p-1$. Since i is odd, $\frac{i(p-1)}{2}$ is not an integer and $\mathbf{J}_p(x) = g^{\frac{i(p-1)}{2}} = \sqrt{1} = \pm{1}$. However, this does not quite match the definition. To continue the proof, we have to prove thatx is a perfect square in $\mathbf{Z}^*_p$ if and only if $x^{\frac{p-1}{2}} = 1 \mbox{ mod } p$:
  $\Rightarrow$ Assume x is a perfect square in $\mathbf{Z}^*_p$, x can be written as $g^{2i} \mbox{ mod } p \mbox{ where } 1 \leq 2i \leq p-1$ and $\mathbf{J}_p(x) = g^{\frac{2i(p-1)}{2}} = g^{i(p-1)} = 1 \mbox{ mod }p$
  $\Leftarrow$ Assume $x^{\frac{p-1}{2}} = 1 \mbox{ mod } p$. Since $x \in \mathbf{Z}^*_p$, x can be written as $g^{i} \mbox{ mod } p$ where $1 \leq i \leq p-1$. Since g is a generator of $\mathbf{Z}^*_p$, g has the order $(p-1)$. Only $g^{p-1} \equiv 1 \mbox{ mod } p$ and $g^i \not\equiv 1 \mbox{ for } i < p-1$. As a result, $(p-1)$  must divide $\frac{i(p-1)}{2}$ and so i is even and x is a perfect square in $\mathbf{Z}^*_p$
  As a result, $\mathbf{J}_p(x) \neq 1$ if x is not a perfect square in $\mathbf{Z}^*_p$ and so $\mathbf{J}_p(x) = -1$

Negligible Function

Introduction:

Modern cryptography concerns about infeasibility rather than impossibility. For example, an encryption scheme is said to be provably secure if the success probability of "breaking" by an adversary is negligibly small rather than zero. Theoretically, the probability is expressed as a probability function of a security parameter k, which is normally the cryptographic key length. Infeasiblity relies on that the success probability function to be a negligible function.

Definition:

A function $f$ is negligible if for every constant $c \geq 0$ there exists an integer $k_c$ such that $f(k) < k^{-c}$ for all $k \geq k_c$

Notes:

The above definition means that the function $f$ is bounded by any positive polynomial fraction. Since for any positive polynomial fraction $g(x)$, we can always find the smallest $c$ such that $k^{-c} \leq g(x)$ for all $k \geq k_c$. Here, by the meaning of $k \geq k_c$, we can also say that the condition holds for a sufficiently large k.

碰碰車

剛剛完成了日文測驗。考完的剎那，我想到了「碰碰車」三個字。何解？「亂撞」是也！

Broadcast Encryption

Broadcast encryption is a scheme which only allows qualified users to decrypt published content. Typically users are separated into subscribed users who have access to the content and unsubscribed users who do not have the access. Conventional broadcast encryption scheme uses a master secret key to encrypt the content which results in only a trusted designer of the system is allowed to produce encrypted content. This type of broadcast encryption is commonly used in Conditional Access System (CAS) such as Cable-TV.

More recently another type of broadcast encryption scheme called public key broadcast encryption was proposed which consists of a system-wide public key. With this public key, every user can produce encrypted content which only a subset of users can decrypt with their own private keys.

明日テストがある

明日日本語のテストがありますが、まだ勉強しません。これから勉強を始めしたら、大丈夫かなと思っています。でも、今度のテストは難しいそうだので、運が必要だとおもっていますね。

iPhone PrivateHeaders

Purpose:

Apple intentionally restricts the access to certain functions of iPhone OS, such as accessing SMS database, by developers using the public SDK for some reasons. However, developing an application which accesses those functions is not impossible because only the header files of those functions are missing in the SDK (The framework in the SDK actually includes those functions). As a result, some developers use some tool to dump those "private headers" from the private framework. Using the dumped headers and the private framework in the SDK, one can develop iPhone application as powerful as Apple can.

Although including the private headers will be much more powerful than using the public header alone, there are other concerns while using private headers. First, there is nearly no information about using private header found on the web. You may be able to find simple tutorials which teach you how to setup a simple project, but to the best of our knowledge, no detailed information like the usage of each function is found (possibly due to the legal concerns of using private headers). In other words, it is like searching in a dark room while trying those headers. Second, since it is like breaking the restrictions set by Apple if you use private header in your application and Apple will examine every piece of application submitted to Apple store, an application which uses private header will certainly not be allowed to be legitimately signed and be published on Apple store. As a result, your application can only run on a jail-broken device.

Preliminaries:

(Here, we assume readers are using OSX and have installed the official iPhone SDK)
You need a tool called "class-dump-z" to dump the required headers from the private framework. Author has tried "class-dump" and "class-dump-x" but the dumped files are worst than the files dumped by "class-dump-z". However, it seems that "class-dump-z" crashes while running on OSX 10.5 Leopard. If you found it crashes on your OSX 10.5 machine, we suggest you try it on a OSX 10.6 machine (like we did, and it runs perfectly on it). Although "class-dump-z" gives us the best result among the tools we tried, the dumped headers cannot be used directly. Some naming conventions and paths must be fixed before using them. Those information can be found on web or by trial and error (mainly fixing the include header's path and name).

Installing Your Application on a Jail-broken Device:

After building your own application, you need to install your application on a (jail-broken) device. If you do not want to do it through Xcode, you may try an unofficial way. As suggested in this site, you can install your application on a jail-broken device via SSH (Sure you have to install OpenSSH package on your device first). The default root password of the jail-broken device is alpine.

Oel ngati kameie

I see you~