"Tuvas" <[EMAIL PROTECTED]> writes: > I have made and recently posted a libary I made to do Modular > Arithmetic and Prime numbers on my website at > http://www.geocities.com/brp13/Python/index.html . I am currently in a > crypotology class, and am working on building a RSA public key > cryptology system for a class project. I am building the librarys just > to get the experience to do so.
I'm looking at http://www.geocities.com/brp13/Python/prime3.html You do something for x in range(10) but you don't use x in the loop. I'll guess you actually intended to pick some random number n and find the closest prime p >= n. That's not a good strategy: imagine you pick a random number n in the range 1..50. Let's say n is 14. 14 isn't prime, so you check 15, 16, and 17. 17 is prime so you return p = 17. You also return 17 if n is 15, 16, or 17. So the chance of your returning p = 17 is 4/50. What is your chance of returning p = 19? It means n has to be 18 or 19, so the chance is only 2/50. That's not good--you want all primes to be equally likely. Anyway, the simplest approach is: 1) get random numbers by reading characters from os.urandom() and converting them to integers. Don't use randint which makes no attempt at cryptographic security. 2) For each random integer (you can set the low bit to make sure it is odd), test against some small prime divisors p (say the primes up to 1000) as a fast way to throw away some composites. If n%p == 0 for any p, throw away n and go back to step 1. 3) If you get an n with no small divisors, do the (slow) Miller-Rabin test. If it passes, you're done; if it fails, go back to step 1. -- http://mail.python.org/mailman/listinfo/python-list
