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.