5b. Modular Arithmetic

Definition: $a\equiv b\mathrm{mod}n⟹$ “is congruent to” Equivalence: If there is an integer k such that $a=n\cdot k+b$.

Definition of a prime number

p integer $\ge 2$ so that the only factor of p are $1,p$

Fast Modular Exponentiation

In relation to RSA Cryptography

• todo

Problem 1

• todo

Problem 2

Repeated multiplication by y takes $d=O(2^n)$ multiplications.

Solution: Compute $y,y^2,y^4,y^8$ reducing mod N each time

$$\begin{array}{r}{y}^1\equiv 2\mathrm{mod}5\\ y^2\equiv 4\mathrm{mod}5\\ y^4\equiv 1\mathrm{mod}5\\ y^8\equiv 1\mathrm{mod}5\end{array}$$

Ask how long do we have? $O(\log d$) times $=O(n)$

function ModExp(y, d, N)
if d = 0, return 1
else compute z = ModExp(y, d/2, N)
if d is even, return y * z^2 (mod N)
if d is odd, return y * z^2 (mod M)*

Running time: $O(logd$ calls to the function) How long does each square take? Either one or two multiplications of $O(n)$ bits.

Running time> $O(n\ast M(N))$ where $M(N)$ is the time to multiply two n-digit numbers.