MATH 470 Lecture 13

« previous | Tuesday, February 26, 2013 | next »

Lagrange's Theorem

(special case) offers a way to check if $a$ is a generator for $(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}{)}^{*}$

If $p$ is prime and $a\in {(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$,

Then ${\mathrm{o}\mathrm{r}\mathrm{d}}_p(a)\mid (p-1)$, where ${\mathrm{o}\mathrm{r}\mathrm{d}}_p(a)$ is the smallest exponent $e\ne 0$ with $a^e\equiv 1(\mathrm{mod}p)$.

Proof. Suppose $k={\mathrm{o}\mathrm{r}\mathrm{d}}_p(a)$. Consider $\ell =\mathrm{G}\mathrm{C}\mathrm{D}(k,p-1)$.

By the Extended Euclidean Algorithm, there are $x,y\in \mathbb{\mathbb{Z}}$ with $kx+(p-1)y=\ell$.

So then

$a^{\ell }\equiv a^{kx+(p-1)y}\equiv 1(\mathrm{mod}p)$

. Since

$\ell \mid k$

(since

$k={\mathrm{o}\mathrm{r}\mathrm{d}}_p(a)$

, we must have

$\ell \ge k$

. By construction,

$\ell \mid k⟹\ell =k$

, so

$k\mid (p-1)$

.

Q.E.D.

Corollary

If $p$ is prime and $a\in (\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}{)}^{*}$ and $a^{\frac{p-1}{q}}\equiv ̸1(\mathrm{mod}p)$ for all primes $q\mid (p-1)$,

Then $a$ is a generator of $\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}{)}^{*}$.

In particular, given a list $\{a_1,\dots ,a_k\}$ of all primes dividing $p-1$, you can check the preceding condition in time $O((\log p{)}^4)$

Note:

1. Life is cruel: you usually do NOT have such a list.
2. If $p-1$ is a product of small primes (to any powers), then life is good!

Proof. We must show that ${\mathrm{o}\mathrm{r}\mathrm{d}}_p(a)=p-1$. By Lagrange's theorem, ${\mathrm{o}\mathrm{r}\mathrm{d}}_p(a)\mid (p-1)$.

So we need to rule out ${\mathrm{o}\mathrm{r}\mathrm{d}}_p(a)$ being a divisor of $p-1$ other than $p-1$.

If $p-1=q_1^{e_1}\dots q_k^{e_k}$ is the factorization of $p-1$, then any $d<p-1$ dividing $p-1$ must divide $\frac{p-1}{q_1}$ or $\frac{p-1}{q_2}$ or ... or $\frac{p-1}{q_k}$.

Now $a^{\frac{p-1}{q}}\equiv ̸1(\mathrm{mod}p)$ for all $q\mid (p-1)$ is equivalent to $a^{\frac{p-1}{q_1}}\equiv ̸1(\mathrm{mod}p-1)$, ..., $a^{\frac{p-1}{q_k}}\equiv ̸1(\mathrm{mod}p-1)$. So if ${\mathrm{o}\mathrm{r}\mathrm{d}}_p(a)<p-1$, it would divide one of $\frac{p-1}{q_1}$ or ... or $\frac{p-1}{q_k}$, which is impossible.

Therefore

${\mathrm{o}\mathrm{r}\mathrm{d}}_p(a)=p-1$

.

Q.E.D.

Complexity Bounds

By Theorem 5.4.1 (of Bach and Shallit), computing $a^e(\mathrm{mod}n)$ takes $O((\log e)({\log }^{}n))$ bit operations. So computing $a^{\frac{p-1}{q}}(\mathrm{mod}p)$ takes $O((\log p{)}^3)$ bit operations. By problem 5 of homework 6, the number of primes dividing $p-1$ is $O(\log p)$

Last Words on RSA

et tu Brute?

To solve problem 1 on the homework, frequency analysis might be useful (decrypt and check that text is in English)

In Ruby,

require 'openssl' base.to_bn.mod_exp(exponent, modulus)

RSA and World Peace

How can the UN monitor Iran's nuclear reactors reliably and still have Iran happy?

Build Good non-tamperable sensors

OR Use RSA as follows: given private large primes $p$ and $q$, private decryption key $d$, public encryption key $e$, and large number $n=pq$

If the sensor reads $x$, transmit $(x,x^d)$.

Iran is happy: they can verify that $x=(x^d{)}^e$ so they know the UN is not transmitting secrets or anything.

The UN is happy: they can compute $x^d$ and check that it really is the supposedly-transmitted $x^d$.

It is hard to mess with $x$ to get $x^{\prime }$ and still have $(x^{\prime }{)}^d=x^d$. If you mess with $x$ and $x^d$, then you need to know $d$!