Safe prime numbers in Python

Scott David Daniels Scott.Daniels at Acm.Org
Wed Jan 14 16:57:55 CET 2004

Skip Montanaro wrote:
>     Tim> Does any know of or have Python code (or C or Fortran code wrapped
>     Tim> as a Python module) for efficiently finding safe prime numbers -
>     Tim> that is a number p such that p and (p-1)/2 are both prime?
> Here's what I came up with using gmpy:
>     import gmpy
>     def safe_primes(last=1):
>         while True:
>             next = gmpy.next_prime(last)
>             if gmpy.is_prime((next-1)/2):
>                 yield next
>             last = next
I suspect it might be faster if you looked for the lower prime:

     def safe_primes(last=1):
         while True:
             last = gmpy.next_prime(last)
             other = last * 2 + 1
             if gmpy.is_prime(other):
                 yield other

-Scott David Daniels
Scott.Daniels at Acm.Org

More information about the Python-list mailing list