MATH 470 Lecture 6

« previous | Tuesday, January 29, 2013 | next »

Euler Totient Function

Very important function in number theory

• It's fundamental in the arithmatic of $\mathbb {Z} /n\mathbb {Z}$ (e.g. Euler's theorem)
• It has fundamental applications in RSA

For any prime $p$ and $k\in \mathbb {N}$,

$\phi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1}$

Proof

To count the number of integers in $\{x,\ldots ,p^{k}-1\}$ that are relatively prime to $p^{k}$, just expand

Any such $x$ in base $p$:

$x=d_{0}+d_{1}\,p+\dots +d_{k-1}\,p^{k-1}$

with

$\left(d_{0},\ldots ,d_{k-1}\right)\in \{0,\ldots ,p-1\}^{k-1}$

where $d_{i}$ is the remainder of $x\div p^{i}-d_{i-1}$

Now $\mathrm {GCD} (x,p^{k})>1\iff GCD(x,p)>1\iff p\mid x\iff d_{0}=0$

There are exactly $p^{k-1}$ numbers with last digit $d_{0}=0$, so therefore

$\phi (p^{k})=p^{k}-p^{k-1}$

Q.E.D.

Lemma

$\phi$ is weakly multiplicative; that is, if $m,n\in \mathbb {Z}$ with GCD(m,n) = 1, then $\phi (m\,n)=\phi (m)\,\phi (n)$

Proof.

Q.E.D.

RSA Review

Start with primes $p$ and $q$ with approx. equal number of digits, and $e\in \left(\mathbb {Z} /p\,q\,\mathbb {Z} \right)^{*}$. Compute $n=p\,q$ and $d$ with $d\,e\equiv 1{\pmod {\phi (n)}}$.

• Public: (n, e)
• Private: (p,q,d)

Why Does Decryption Work?

$c=m^{e}{\pmod {n}}$

Why is $c^{d}=m$?

Proof.

${\begin{aligned}c^{d}&=(m^{e})^{d}\\&=m^{de}{\pmod {n}}\\&=m^{1+N\phi (n)}{\pmod {n}}&{\text{by construction}}\\&=m((m)^{\phi (n)})^{N}{\pmod {n}}\\&=m\cdot 1^{N}{\pmod {n}}&{\text{by Euler}}\\&=m{\pmod {n}}\end{aligned}}$

How to break RSA If you can factor $n$ (which is a(n) (apparently) very difficult to do, by the way), then you can get $p$ and $q$. You can then do this:

1. Compute $\phi (n)=(p-1)(q-1)$
2. Solve $d\,e\equiv 1{\pmod {\phi (n)}}$ for $d$
3. Doing the Extended Euclidean Algorithm is much faster than factoring!!!

If you gnow $\phi (n)$, you can do the same...

Oddly, computing $\phi (n)$ and factoring $n$ are actually almost equivalent complexity!

Lemma

If $n=p\,q$ for primes $p$ and $q$, then $p$ and $q$ are exactly the roots of $x^{2}-\left(n-\phi (n)+1\right)\,x+n=0$

Proof.

${\begin{aligned}n-\phi (n)+1&=p\,q-(p-1)(q-1)+1\\=p+q\end{aligned}}$

Our quadratic = $x^{2}-(p-q)x+p\,q$

Quadratics are easy to solve approximately over $\mathbb {R}$, but square roots are hard to calculate in $\left(\mathbb {Z} /n\mathbb {Z} \right)^{*}$

Chinese Remainder Theorem

If $m$ and $n$ are relatively prime integers and $a$ and $b$ are any integers, then the simultaneous congruences

${\begin{aligned}x&\equiv a{\pmod {m}}\\x&\equiv b{\pmod {n}}\end{aligned}}$

have a unique solution, in particular in $\mathbb {Z} /mn\mathbb {Z}$

$x\equiv a\,n\left({\frac {1}{n}}{\pmod {m}}\right)+b\,m\left({\frac {1}{m}}{\pmod {n}}\right){\pmod {m\,n}}$

Proof

Proof. (The formula works)

the stated formula, mod $m$, reduces to:

$x\equiv a\,n\left({\frac {1}{m}}{\pmod {m}}\right)\equiv a{\pmod {m}}$

Similarly, mod $n$, reduces to:

$x\equiv b{\pmod {n}}$

Uniqueness: if $x_{1},x_{2}\in \mathbb {Z} /mn\mathbb {Z}$ are both solutions, then

${\begin{aligned}x_{1}-x_{2}&\equiv 0{\pmod {m}}\\x_{1}-x_{2}&\equiv 0{\pmod {n}}\\m&\mid (x_{1}-x_{2})\\n&\mid (x_{1}-x_{2})\\m\,n&\mid (x_{1}-x_{2})\\x_{1}-x_{2}&\equiv 0{\pmod {m\,n}}\end{aligned}}$

Example

If you have fewer than 255 books and

• after stacking by 15, you have 3 leftovers
• after stacking by 17, you have 4 leftover

How many books do you have?

Let $n$ be the number of books. Equivalently, ${\begin{aligned}n\equiv 3{\pmod {15}}\\n\equiv 4{\pmod {17}}\end{aligned}}$

Therefore,

${\begin{aligned}n&=3\cdot 17\cdot \left({\frac {1}{17}}{\pmod {15}}\right)+4\cdot 15\cdot \left({\frac {1}{15}}{\pmod {17}}\right)\\&=3\cdot 17\cdot 8+4\cdot 15\cdot (-9)\\&=123\end{aligned}}$

Kerckhoffs' Principle

(See wikipedia:Kerckhoffs's principle→)

Any cryptosystem should remain secure even if all (except key) is known.

(c.f. security by obscurity)

This is why RSA is so good.

Complexity

How hard is it to...

• multiply two $d$-digit integers? ($\leq 10\,d\,\log _{2}{(d)}\,\log _{2}{(\log _{2}{(d)})}$ bit operations)
• reduce one $d$-digit integer mod another? ($\leq 17\,d\,\log _{2}{(d)}\,\log _{2}{(d)}\,\log _{2}{(\log _{2}{(d)})}$ bit operations)
• compute $a^{e}{\pmod {n}}$? ($O\left(\log {e}\,(\log {n})^{2}\right)$)

$\leq 10\,d\,\log _{2}{(d)}\,\log _{2}{(\log _{2}{(d)})}$ seems beeter than $O(d^{2})$. For large $d$, you want to NOT use the grade school multiplication algorithm. Use this instead.

Rule of thumb: case approx. number of digits:

• < 100: grade school is best.
• 100..200: Karatsuba
• > 200: FFT

Note: Architecture matters:

• Humans: Grade school multiplication is best for fewer than 4 digits (with some tricks), anything beyond we use computers
• Computer: Depending on chips/memory, number of digits dictates the algorithm.

Bit Operation?

• bit-by-bit operation: 1+1, 1×0, shift by a bit
• (with some constancy) digit-by-digit operation

Big-Oh Notation

(See Asymptotic Analysis→)

We say two functions $f,g:\mathbb {Z} \to \mathbb {R}$ satisfying $f=O(g)$ iff there are constants $c,m>0$ with

$\left|f(x)\right|\leq m\left|g(x)\right|\quad \forall x\geq C$

Example:

• Grade school, every digit is multiplied by every other digit with added carry digits. $O(d^{2})$.
• Gaussian Elimination takes $O(n^{3})$ arithmetic operations to reduce an $n\times n$ matrix to row-echelon form.

Until Next Time

Quiz on Tuesday

Be able to compute stuff like $a^{e}{\pmod {n}}$

• use Fermat's Little Theorem or Euler's theorem