[Edu-sig] Cryptonomicon (concluding remarks re rsa.py)

[Kirby Urner]

Not to get too boring with a lot of source code, but I just
wanted to tentatively conclude this thread by saying I appear
to be getting those 100-digit randomly generated primes in
a few seconds (thanks again to Tim Peters).

The theory here is if I get two such primes (p,q) and 
multiply them together to get n (=p*q), then n will clearly
be composite, but you won't be able to factor it in any 
reasonable amount of time -- i.e. it's not an easily 
reversible operation to "crack" a giant composite back into 
those two 100-digit primes.  Upon this theory, the security 
of RSA -- and some other enciphering schemes -- is based.

Exactly how p,q and n are used to generate the public/private
key pairs is something for another post (and/or it's all over
the web, so maybe best to not continue this on edu-sig -- 
my goal was proof of concept, i.e. to show how Python helps 
make this kind of applied number theory more accessible, in
the context of our more culturally-aware secondary school 
curricula).

 >>> p = rsa.bigppr(100)  # p = 100-digit probable prime
 0.999999999999 chance of being prime
 Elapsed time: 11.7096741481 seconds
 >>> q = rsa.bigppr(100)  # q = another, likewise random
 0.999999999999 chance of being prime
 Elapsed time: 11.8497435425 seconds
 >>> p*q                  # multiply p and q together
 6219322243149162742872969564458220474602406043133576977435414
 2015617576401568043346146450800258375839374620140328507945422
 3449745045986064300468648593012781115111325338623954089338598
 9636778527561983357L
 >>> rsa.ppt(p*q)         # ppt says p*q is composite (it is)
 0

Note:  I haven't verified that my implementation of Miller-Rabin
is 100% correct (I'm still getting "peer-reviewed" here), but I 
note it does seem to work right when run against low primes, e.g.:

 >>> import primes
 >>> plist = filter(lambda x: x>5000, primes.erastosthenes(5100))
 >>> plist
 [5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099]
 >>> filter(lambda x: rsa.ppt(x,10), range(5000,5100))
 [5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099]

ppt (probable prime test) uses essentially the same code as I posted 
in: http://mail.python.org/pipermail/edu-sig/2000-December/000827.html
(which is in turn based on that 1997 BA thesis by Pete Emerson at 
Middlebury College, URL given in that post).  If you see an error
in my code, or have suggestions for making it better/faster (w/o 
losing the "pure Python" feature), I'm happy to read them.

Kirby