Safe Prime

A safe prime is a prime number of the form 2p + 1, where p is also a prime. (Conversely, the prime p is a Sophie Germain prime.) The first few safe primes are

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, ... (sequence A005385 in OEIS)

With the exception of 7, a safe prime q is of the form 6k − 1 or, equivalently, q ≡ 5 (mod 6) — as is p > 3 (c.f. Sophie Germain prime, second paragraph). Similarly, with the exception of 5, a safe prime q is of the form 4k − 1 or, equivalently, q ≡ 3 (mod 4) — trivially true since (q − 1) / 2 must evaluate to an odd natural number. Combining both forms using lcm(6,4) we determine that a safe prime q > 7 also must be of the form 12k−1 or, equivalently, q ≡ 11 (mod 12).

Read more about Safe Prime:  Applications, Further Properties, Records

Famous quotes containing the words safe and/or prime:

    It is safe to say that no other superstition is so detrimental to growth, so enervating and paralyzing to the minds and hearts of the people, as the superstition of Morality.
    Emma Goldman (1869–1940)

    And this must be the prime of life . . . I blink,
    As if at pain; for it is pain, to think
    This pantomime
    Of compensating act and counter-act,
    Defeat and counterfeit, makes up, in fact,
    My ablest time.
    Philip Larkin (1922–1986)