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~