## Sophie Germain Primes

### August 6, 2013

A prime number p is a Sophie Germain prime if 2p+1 is also prime. The list of Sophie Germain primes begins 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, (A005384); it is not known if the list is infinite. Sophie Germain primes are named after the French mathematician Marie-Sophie Germain, who in 1825 proved Fermat’s last theorem for such primes; thus, if p is a Sophie Germain prime, then there do not exist integers x, y and z not equal to zero and not a multiple of p such that xp + yp = zp.

One way to find Sophie Germain primes is to enumerate the primes p and check the primality of each 2p+1. That works fine for relatively small p. For larger p, amateur mathematician Harvey Dubner developed a sieve that speeds finding Sophie Germain primes:

Define the three polynomials fp(c) = c * 3003 * 10b – 1, fq(c) = 2 fp(c) + 1, and fr(c) = (fp(c) – 1) / 2. Choose b which is the approximate number of digits for the range of Sophie Germain primes you are searching.

Sieve each of the polynomials over the range 1 ≤ cm for some suitable m. Use as sieving primes the primes greater than 13 but less than some suitable f which is conveniently large but much less than the square root of fp(1). All three polynomials are sieved over the same sieving array. Sieving is done in a similar manner to sieving the polynomials in the multiple polynomial quadratic sieve.

After sieving is complete, apply a primality test to each fp(c) that survived all three sievings. If it is prime, check both fq(c) and fr(c) for primality. If fq(c) is prime, then fp(c) is a Sophie Germain prime. If fr(c), then fr(c) is a Sophie Germain prime.

Your task is to write a sieve that finds Sophie Germain primes as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2
{"ft_lang_label":"__label__en","ft_lang_prob":0.87808985,"math_prob":0.9720741,"size":1898,"snap":"2019-43-2019-47","text_gpt3_token_len":509,"char_repetition_ratio":0.17476241,"word_repetition_ratio":0.011363637,"special_character_ratio":0.26606956,"punctuation_ratio":0.113300495,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9771352,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-11-13T13:38:38Z\",\"WARC-Record-ID\":\"<urn:uuid:a1e8d74f-80d9-41ce-88e6-67c38fbbcd67>\",\"Content-Length\":\"80174\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:8b9e67ca-b0d6-4946-a2cb-75799bba6003>\",\"WARC-Concurrent-To\":\"<urn:uuid:56fc8f48-e288-4891-bb77-a22510de1033>\",\"WARC-IP-Address\":\"192.0.78.24\",\"WARC-Target-URI\":\"https://programmingpraxis.com/2013/08/06/sophie-germain-primes/\",\"WARC-Payload-Digest\":\"sha1:3KJ5DJ73ZX2F7OTLN2K52FOQJZWAB2OS\",\"WARC-Block-Digest\":\"sha1:OOTAY3SCSIT6YAZ7ATVVETP5KFBVQTE7\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-47/CC-MAIN-2019-47_segments_1573496667260.46_warc_CC-MAIN-20191113113242-20191113141242-00111.warc.gz\"}"}