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:

    If the vice president thinks it’s disgraceful for an unmarried woman to bear a child, and if he believes that a woman cannot adequately raise a child without a father, then he’d better make sure that abortion remains safe and legal.
    Diane British (b. 1948)

    Ay, look: high heaven and earth ail from the prime foundation;
    All thoughts to rive the heart are here, and all are vain:
    Horror and scorn and hate and fear and indignation—
    Oh, why did I awake? When shall I sleep again?
    —A.E. (Alfred Edward)