Safe prime numbers in Python

[Scott David Daniels]

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