Those cards are at it again. The quest to cut down the complexity of possible primes in Wonderland continues. Having been previously burnt modulo 4 the Queen of Hearts decided to move to modulo 6 ; henceforth only those primes of the form p ≡ 1 (mod 6)would be used in Wonderland. The existence of all others would be denied. The Queen of course checked and indeed there seemed to be many such values; 7, 19, 31, 37, . . .. Of course “safe” or “strong primes” were still desirable and the White Rabbit was set the task of finding such primes 1 modulo 6 . In fact the quest was for Sophie Germain primes: primes p for which 2p + 1 is also prime. These offer the least information for the Pohlig-Hellman algorithm to effectively function for example and have other cryptographic purposes . Rabbit had been assured by the Mad Hatter that this should be easy. Hatter’s argument went as follows; no less than G. H Hardy had conjectured, and given supporting mathematical reasons, that the asymptotic behaviour of the number of Sophie Germain primes has the value π SG (x) ≈ Cx/(log x) 2 . If this were true and since primes of the form ±1 (mod 6) in the Queen’s mandated list make up approximately half of all possible primes, the same should be true of Germain primes; merely a factor of two different. The March Hare wasn’t so sure; he didn’t like these hand-waving kinds of argument and didn’t trust the Hatter’s logic. Can you help the folks in Wonderland out?

If p is a Sophie Germain prime with p ≡ 1 (mod 6) then p = 6k + 1 for some integer k . Then q = 2p + 1 = 2(6k + 1) + 1 = 12k + 3 and this is clearly divisible by 3 and so cannot be prime. Thus all Sophie Germain primes are of the form p ≡ 5 (mod 6)