Random Prime Generator/Modular Arithmetic

Tuvas tuvas21 at gmail.com
Sat Mar 4 17:55:52 EST 2006


Okay, I don't know if your farmiliar with the miller-rabin primality
test, but it's what's called a probabalistic test. Meaning that trying
it out once can give fake results. For instance, if you use the number
31 to test if 561 is prime, you will see the results say that it isn't.
Mathematically, the most possible wrong answers is 1/4th of the
numbers. Thus, one should try at least 10 times (A very standard value)
in order to ensure that the number is not a psuedoprime, but indeed a
real prime number. That was the intent of the loop of 10 without using
the number.

If this test fails, it will chose another random number to test.

I could easily test with several small numbers, at least primes up to
20 would greatly reduce the number of miller-rabin tests to perform,
and would speed up the process considerably. Might as well toss it in.

Thanks for the tip on the urandom. I knew there had to be a better
random number generator somewhere. I saw lots of stuff for os specific,
but I'm trying to develop this as os independent.




More information about the Python-list mailing list