Correctness proof sketch

show that both sides of the following equation are divisible by the other side $gcd(a,b) = gcd(b, a \%b)$ can use the fact that $a\%b = a - b\cdot floor(a/b)$ and also that when $x|p$ and $x|q$ then $x|gcd(p,q)$.

Proof 1

We will show that the function is really a bijection.

injective

Suppose $f(x) = f(y)$, then from the linearity $f(x-y) = \mathbf{0}$. Thus $\forall N_i:x-y |N_i$ and $x-y | N$ and because $x,y \in Z_N$ we have that $x-y = 0$. $f$ is a homomorphism between two sets with the same cardinality and because it is injective it is surely also surjective and therefore bijective.

Proof 2 constructive (for two equations)

Suppose we have $f(u_1) = (1,0)$, $f(u_2) = (0,1)$ then $f(a_1u_1+a_2u_2 \mod{N})=a_1f(u_1)+a_2f(u_2) = (a_1, a_2)$.

But how to find $u$?

Let $f(N_2 ) = (z, 0)$. If $z\neq 1$ we must put in little bit more work. But all we need to do is notice that we can take a multiplicative inverse of $z \mod{N_1}$ because $z$ is surely coprime to it, from this we get that $u_1 = N_2 \cdot z^{-1}$, similarly for $u_2$.

Proof 3 (similar to proof 2)

There surely exists $N_1^{-1} \mod{N_2}, N_2^{-1} \mod{N_1}$ because $N_i$s are coprime. Then we claim that the following solves the system $$y = a_1N_2N_2^{-1} + a_2N_1N_1^{-1} \mod{N_1 N_2}$$

Why? Let’s just show it only for $x_1$: $$y \mod{N_1} = a_1 + 0$$ The last thing we need to do is show that this solution is unique. But this can be shown in the way that was presented in the first proof.

Calculating $\varphi(N)$

for coprime $x, y$ because $$Z_{xy}\rightarrow Z_{x} \times Z_y$$ we count in the first and then in the second.

Interestingly for not coprime $x, y$ $$\varphi(xy) = \varphi(x) \varphi(y) \frac{gcd(x,y)}{\varphi(gcd(x,y))}$$

Factoring

No poly. Several subexpo. Polynomial quantum (Shore 1994).

Primality testing

“easy”. Fast probabilistic algos. Deterministic poly (Agarval et al. 2002) is not really usable in practice.

Fermat test

Fermat test for $N \in Z$

• Generate $a \in_R Z_{N}$.
• If $a$ divides $N$ say NO. (Euclid witness)
• If $a^{N-1} \neq 1$ say NO. (Fermat witness)
• YES.

If N is not Carmichael then $$H := \{x \in Z^*_N| x^{N-1} = 1 \mod{N}\}$$ This is a subgroup of $Z^*_N$ and $H \neq Z^*_N$, thus $|H| \leq \frac{|Z^*_N|}{2}$, which implies that $$Pr[\text{x witness}] \geq 1/2$$

Generating primes

Primality tests can be used for it. Expected number of tries: $$\Theta(b)$$