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{\mathbb{Z}}/n\mathbb{\mathbb{Z}}$ (e.g. Euler's theorem)
• It has fundamental applications in RSA

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

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

Proof

To count the number of integers in $\{x,\dots ,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

$(d_0,\dots ,d_{k-1})\in \{0,\dots ,p-1{\}}^{k-1}$

where $d_i$ is the remainder of $x÷p^i-d_{i-1}$

Now $\mathrm{G}\mathrm{C}\mathrm{D}(x,p^k)>1⟺GCD(x,p)>1⟺p\mid x⟺d_0=0$

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

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

Q.E.D.

Lemma

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

Proof.

Q.E.D.

RSA Review

Start with primes $p$ and $q$ with approx. equal number of digits, and $e\in {(\mathbb{\mathbb{Z}}/pq\mathbb{\mathbb{Z}})}^{*}$. Compute $n=pq$ and $d$ with $de\equiv 1(\mathrm{mod}\varphi (n))$.

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

Why Does Decryption Work?

$c=m^e(\mathrm{mod}n)$

Why is $c^d=m$?

Proof.

$\begin{array}{rl}{c}^d& =(m^e{)}^d\\ & =m^{de}(\mathrm{mod}n)\\ & =m^{1+N\varphi (n)}(\mathrm{mod}n)& \text{by construction}\\ & =m((m{)}^{\varphi (n)}{)}^N(\mathrm{mod}n)\\ & =m\cdot 1^N(\mathrm{mod}n)& \text{by Euler}\\ & =m(\mathrm{mod}n)\end{array}$

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 $\varphi (n)=(p-1)(q-1)$
2. Solve $de\equiv 1(\mathrm{mod}\varphi (n))$ for $d$
3. Doing the Extended Euclidean Algorithm is much faster than factoring!!!

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

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

Lemma

If $n=pq$ for primes $p$ and $q$, then $p$ and $q$ are exactly the roots of $x^2-(n-\varphi (n)+1)x+n=0$

Proof.

$\begin{array}{rl}n-\varphi (n)+1& =pq-(p-1)(q-1)+1\\ =p+q\end{array}$

Our quadratic = $x^2-(p-q)x+pq$

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

Chinese Remainder Theorem

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

$\begin{array}{rl}x& \equiv a(\mathrm{mod}m)\\ x& \equiv b(\mathrm{mod}n)\end{array}$

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

$x\equiv an\left(\frac{1}{n}(\mathrm{mod}m)\right)+bm\left(\frac{1}{m}(\mathrm{mod}n)\right)(\mathrm{mod}mn)$

Proof

Proof. (The formula works)

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

$x\equiv an\left(\frac{1}{m}(\mathrm{mod}m)\right)\equiv a(\mathrm{mod}m)$

Similarly, mod $n$, reduces to:

$x\equiv b(\mathrm{mod}n)$

Uniqueness: if $x_1,x_2\in \mathbb{\mathbb{Z}}/mn\mathbb{\mathbb{Z}}$ are both solutions, then

$\begin{array}{rl}{x}_1-x_2& \equiv 0(\mathrm{mod}m)\\ x_1-x_2& \equiv 0(\mathrm{mod}n)\\ m& \mid (x_1-x_2)\\ n& \mid (x_1-x_2)\\ mn& \mid (x_1-x_2)\\ x_1-x_2& \equiv 0(\mathrm{mod}mn)\end{array}$

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{array}{r}n\equiv 3(\mathrm{mod}15)\\ n\equiv 4(\mathrm{mod}17)\end{array}$

Therefore,

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

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? ($\le 10d{\log }_2(d){\log }_2({\log }_2(d))$ bit operations)
• reduce one $d$-digit integer mod another? ($\le 17d{\log }_2(d){\log }_2(d){\log }_2({\log }_2(d))$ bit operations)
• compute $a^e(\mathrm{mod}n)$? ($O(\log e(\log n{)}^2)$)

$\le 10d{\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{\mathbb{Z}}\to \mathbb{ℝ}$ satisfying $f=O(g)$ iff there are constants $c,m>0$ with

$|f(x)|\le m|g(x)|\mathrm{\forall }x\ge 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(\mathrm{mod}n)$

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