Random Prime Generator/Modular Arithmetic

[Astan Chee]

thanks for the webpage info,
however theres a small error I found when trying to generate a prime 
number with more than 300 decimal digits. It comes up with

File "prime.py", line 84, in mod_square_pow
    return x*mod_square_pow(((a**2)%n),t,n,p*2)
  File "prime.py", line 84, in mod_square_pow
    return x*mod_square_pow(((a**2)%n),t,n,p*2)
  File "prime.py", line 73, in mod_square_pow
    if(p*2>t):
RuntimeError: maximum recursion depth exceeded in cmp

Have you considered this? otherwise the algorithm is rather quick for 
generating large random prime numbers.
Thanks for your help

Tuvas wrote:

>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.
>
>  
>