next up previous
Next: Quantum Simulation Up: RSA Previous: RSA

``Proofs"

We will prove that $\left(M^{(p-1)(q-1)}\right)_{mod~R}=1$. Then $
\left(M^{s(p-1)(q-1)+1}\right)_{mod~R}=M$ for all $s$, and thus if $de=s(p-1)(q-1)+1$, $(M^{de})_{mod~R}=M$.

We first prove that if $p$ is a prime, then $(a^{p-1})_{mod~p}=1$.

Consider the set $\{ 1,a_{mod~p},(a^2)_{mod~p},...,(a^{r-1})_{mod~p}\}$, where $r$ is the smallest value such that $(a^r)_{mod~p}=1$. (Such a value must exist since the number of possible values for $(a^s)_{mod~p}$ is limited by the numbers less than $p$. Thus at some point two of these powers, say $s$ and $t$ we must have $(a^s)_{mod~p}=(a^t)_{mod~p}$ (I assume $s>t$). Thus $
((a^s)-(a^t)) =(a^t)(a^{s-t}-1)$ must be a multiple of p. Since by assumption $a$ does not have $p$ as a factor, neither does $a^t$, and thus $a^{s-t}-1$ must have $p$ as a factor. This implies that $a^{s-t}_{mod~p} =1$.)

The set of all powers of $a$ is a subgroup of the group of all numbers from 1 to $p-1$ under multiplication. We now rely on the theorem of group theory that the size of a subgroup always evenly divides the size of the group itself. That means that r must evenly divide $p-1$, and thus $(a^{p-1})_{mod~p}=(a^{rt})_{mod~p}=(((a^r)_{mod~p})^t)_{mod~p}= 1^t=1$ Note that this theorem is true, even if $a$ is greater than $p$. Thus for any $a$, $a^{p-1}=sp+1$ for some integer $s$.

We now show that $(M^{(p-1)(q-1)})_{mod~R}=1$. Using $M^{p-1}=sp+1$ and using the binomial theorem, we have

$\displaystyle (M^{(p-1)(q-1)})$ $\textstyle =$ $\displaystyle (M^{(p-1)})^{(q-1)}
=\left( sp+1\right)^{(q-1)}$  
  $\textstyle =$ $\displaystyle (1^{q-1} +{q-1\over 2}1^{q-2}sp +....+(sp)^{q-1}=1+pt$ (24)

for some $t$. Similarly, $(M^{q-1})^{p-1}=1+qt'$ for some $t'$. Thus $pt=qt'$, and $t$ must have $q$ as a factor, or $t=t''q$. This gives $(M^{(p-1)(q-1)}= t''pq+1$ or $\left(M^{(p-1)(q-1)}\right)_{mod~pq}=1$ as required.


next up previous
Next: Quantum Simulation Up: RSA Previous: RSA
Bill Unruh
2000-03-15