Primes....

[Paul Rubin]

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