Dominik Farhan

Math

Arithmetics on b-bit numbers

Euclid

O(bb3)\mathcal{O}(b \cdot b^3), improvable to quadratic.

Correctness proof sketch

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

We should know Bezeout coefficients and how to compute them. More on it here.

Extension of the Euclid algorithm can compute inverses.

Euler’s Theorem

"Intuitively it’s clear, less intuitively it’s the Lagrange’s Theorem" — Martin Mareš

We want to prove that: N:x coprime to N:xφ(N)=1(mod N)\forall N: \forall x \text{ coprime to } N: x^{\varphi(N)} = 1 (\text{mod N})

Monsieur Lagrange said that for a finite group G and H its subgroup the size of H divides the size of G.

Now let’s have the following sequence: x0,x1,,xk1,1x^0, x^1, \dots, x^{k-1}, 1 we are in ZN\mathbb{Z^*_N} so surely after some number of steps some number repeats. The first repeated number is one that comes from the following xi=xjx^i = x^j xji=1x^{j-i} = 1 now the sequence forms a subgroup of ZN\mathbb{Z^*_N} thus kφ(N)k| \varphi(N) φ(N)=kl\varphi(N) = k\cdot l from here it should be straightforward.

Chinese Remainder Theorem

Let N1,N2,...,NkN_1, N_2, ..., N_k be coprime then the following system of equations xi=aimodNix_i = a_i \mod{N_i} has exactly one unique solution in ZNZ_N, where NN is the product of all NiN_is.

A different view on this is that there is a function f:ZNXiZNif: Z_N \rightarrow \mathbf{X}_i Z_{N_i} this function is a ring isomorphism.

Proof 1

We will show that the function is really a bijection.

injective

Suppose f(x)=f(y)f(x) = f(y), then from the linearity f(xy)=0f(x-y) = \mathbf{0}. Thus Ni:xyNi\forall N_i:x-y |N_i and xyNx-y | N and because x,yZNx,y \in Z_N we have that xy=0x-y = 0. ff 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(u1)=(1,0)f(u_1) = (1,0), f(u2)=(0,1)f(u_2) = (0,1) then f(a1u1+a2u2modN)=a1f(u1)+a2f(u2)=(a1,a2)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 uu?

Let f(N2)=(z,0)f(N_2 ) = (z, 0). If z1z\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 zmodN1z \mod{N_1} because zz is surely coprime to it, from this we get that u1=N2z1u_1 = N_2 \cdot z^{-1}, similarly for u2u_2.

Proof 3 (similar to proof 2)

There surely exists N11modN2,N21modN1N_1^{-1} \mod{N_2}, N_2^{-1} \mod{N_1} because NiN_is are coprime. Then we claim that the following solves the system y=a1N2N21+a2N1N11modN1N2y = a_1N_2N_2^{-1} + a_2N_1N_1^{-1} \mod{N_1 N_2}

Why? Let’s just show it only for x1x_1: ymodN1=a1+0y \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 φ(N)\varphi(N)

φ(p)=p1\varphi(p) = p-1 φ(pk)=(11/p)pk=pk1(p1)\varphi(p^k) = (1-1/p)p^k = p^{k-1}(p-1) φ(xy)=φ(x)φ(y)\varphi(xy) = \varphi(x) \varphi(y)

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

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

Factoring vs Primality testing

generally the former is a lot harder.

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 NZN \in Z

  • Generate aRZNa \in_R Z_{N}.
  • If aa divides NN say NO. (Euclid witness)
  • If aN11a^{N-1} \neq 1 say NO. (Fermat witness)
  • YES.

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

Rabin-Miller test

More on the Rabin-Miller test (and also Fermat ) here.

Generating primes

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

Discrete logs and discrete square roots

I don't have notes for those two topics altough they were covered in lectures. Please refer to boards (or notes in czech) by Martin Mareš.