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:
“We fight our way through the massed and leveled collective safe taste of the Top 40, just looking for a little something we can call our own. But when we find it and jam the radio to hear it again it isn’t just ours—it is a link to thousands of others who are sharing it with us. As a matter of a single song this might mean very little; as culture, as a way of life, you can’t beat it.”
—Greil Marcus (b. 1945)
“One wants in a Prime Minister a good many things, but not very great things. He should be clever but need not be a genius; he should be conscientious but by no means strait-laced; he should be cautious but never timid, bold but never venturesome; he should have a good digestion, genial manners, and, above all, a thick skin.”
—Anthony Trollope (1815–1882)