Primes....

Paul Rubin phr-n2002a at nightsong.com
Wed Mar 27 09:13:22 EST 2002


"FREDRIK HULDTGREN" <tdi01fhu at syd.kth.se> writes:

> I should have been more specific, yes I am talking about cryptology, and
> sadly enough I am runnign win2k, the unix stuff goes out the window. As
> for how large of numbers I am looking for, I'd say about 512bit numbers
> should do it(perhaps larger, depens on how slow it becomes). Got any
> URLs that explain Fermat/Miller-Rabin tests?

Fermat test:

  def probably_prime(n,base=3):
     return pow(base,n,n)==base

For cryptography sized random numbers this is basically 100% accurate.

The unix stuff just pertains to reading random #'s from /dev/urandom.
If you're running cygwin, that emulates it so it should still work.
Otherwise write a C extension that calls CryptGenRandom from the
Windows CAPI.  I'm hoping someone will submit a module that does that
to the Python library.



More information about the Python-list mailing list