## Supplementary material for the |
---|

The following routine has `Maple` compute primes P and Q, and a pair of
encryption/decryption exponents e and d, given an integer n. P and Q
will be n decimal digits long.

RSA:=proc(n) local P,Q,frog,T,R,S,toad,zebra; P:=3;Q:=5; while(type(2*n-length(P*Q),positive) and P<>Q) do frog:=rand(10^(n-1)..10^n-1); P:=nextprime(frog()); Q:=nextprime(frog()) od; T:=(P-1)*(Q-1); toad:=rand(10^iquo(2*n,4)..10^(3*iquo(2*n,4))); R:=T; while(igcd(T,R)>1) do R:=toad(); zebra:=msolve(R*S=1,T) od;assign(zebra); RETURN(P,Q,P*Q,R,S); end;You can copy this and try it yourself. Here is one use of this routine:

>RSA(15); 481321110693277, 397474256143567, 191312750439005747675813699059, 305613921751630036805, 163151755562420097036265148189The first two numbers are fifteen decimal digit primes, and the third number is the product of the primes. The last two numbers are the encryption and decryption exponents. Alice in this case would

There's one more computational wrinkle. How "hard" (in turns of
time or number of operations) is
exponentiation? Direct computation takes a long time. For
example, the command

`2^1234567 mod 10000000000000000039;`

on my PC took over one and a half seconds. The numbers actually used
in "real" RSA are much bigger.
There is a shortcut, though, which I will explain in class (or see section
5.7 in the notes, beginning on p. 24). `Maple` uses this
shortcut if you write exponentiation slightly differently. The command

`2&^7654321 mod 10000000000000000039;`

which also exponentiates took less than one-hundredth of a second to
compute! The ampersand (&) before the caret (^) uses the faster
exponentiation method.

How long does this program take? Please note that `Maple`
generally doesn't run fast, and this code is *not*
optimized. Here is how long RSA(n) for various n's on my
desktop PC:

# of decimal places (n) | Time in seconds |
---|---|

10 | .01 |

20 | .02 |

50 | .059 |

100 | .066 |

150 | 8.48 |

So even for a terrible implementation on a not-so-fast computer, creating two 100-decimal digit primes, etc., takes less than a second.