Random Prime Generator/Modular Arithmetic

[Paul Rubin]

"Tuvas" <tuvas21 at gmail.com> 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.