Primes....

[FREDRIK HULDTGREN]

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?

/Fredrik

>>> Paul Rubin <phr-n2002a at nightsong.com> 03/26/02 21:43 PM >>>
"FREDRIK HULDTGREN" <tdi01fhu at syd.kth.se> writes:

> I am looking for a way(either by finding a module online, or by
getting
> some helpfull hints on how to write this myself) to generate **large**
> prime numbers. All help is appreciated(Id rather write the code myself
> since I tend to like understanding the code that I use, but if the
math
> is too heavy I'll have to use other code...)

How large is large?  If you're trying to do cryptography, just
generate random odd numbers of the size you want, do some trial
divisions to eliminate candidates with small divisors, then do a
few Fermat or Miller-Rabin tests, til you get a prime.  Of course
if you have gmpy, just do this:

    import gmpy,secrand
    def getprime(nbytes):
        while 1:
            p=secrand.getlong(nbytes) | 3
            if gmpy.is_prime(p): return p
       
where secrand.py (for unix/linux) is as follows:

    # Secure random number generator

    # Copyright 2001 Paul Rubin, Fort GNOX Cryptography
    # Copying permissions: GNU General Public License version 2.

    # $Id: secrand.py,v 1.5 2001/09/21 07:10:44 phr Exp phr $

    class _secrand:
        def __init__(self):
            self.__f = open("/dev/urandom")
        def getbytes(self,nbytes):
            return self.__f.read(nbytes)
        def gethex(self,nbytes):
            import binascii
            return binascii.hexlify(self.getbytes(nbytes))
        def getlong(self,nbytes):
            return long(self.gethex(nbytes), 16)

    secrand = _secrand()

If you're trying to break the world record for finding the largest
known prime, you'd normally look at special types of numbers (Mersenne
numbers) and use some special algorithms for recognizing them and
doing the arithmetic.  It's not really practical to do that in Python.
-- 
http://mail.python.org/mailman/listinfo/python-list