A safe prime is a prime number that stays linked to another prime when 1 is subtracted and the result is divided by 2. In other words, a prime number p is safe when (p − 1) / 2 is also prime.
Definition
A safe prime is a prime number p such that there is another prime number q with:
p = 2q + 1
The prime q is called a Sophie Germain prime. So safe primes and Sophie Germain primes are paired by the formula p = 2q + 1.
Safe Prime Formula
Safe Prime Condition
p is a safe prime if p is prime and (p − 1) / 2 is prime.
The definition has two separate prime conditions. The number p must be prime, and the smaller number q = (p − 1) / 2 must also be prime. If either one is composite, p is not a safe prime.
p
The larger prime being tested as a safe prime.
q
The smaller prime where q = (p − 1) / 2.
Link
If q is prime and 2q + 1 is prime, then 2q + 1 is safe.
Examples of Safe Primes
The first safe primes are 5, 7, 11, 23, 47, 59, 83, 107, 167, and 179. Each one works because both p and q are prime.
| Safe Prime p | q = (p − 1) / 2 | Why It Works |
|---|---|---|
| 5 | 2 | 5 is prime, and 2 is prime. |
| 7 | 3 | 7 is prime, and 3 is prime. |
| 11 | 5 | 11 is prime, and 5 is prime. |
| 23 | 11 | 23 is prime, and 11 is prime. |
| 47 | 23 | 47 is prime, and 23 is prime. |
| 59 | 29 | 59 is prime, and 29 is prime. |
| 83 | 41 | 83 is prime, and 41 is prime. |
| 107 | 53 | 107 is prime, and 53 is prime. |
| 167 | 83 | 167 is prime, and 83 is prime. |
| 179 | 89 | 179 is prime, and 89 is prime. |
Safe Primes and Sophie Germain Primes
Safe primes are closely tied to Sophie Germain primes, but the two terms describe different numbers in the same pair.
| Term | Meaning | Example |
|---|---|---|
| Sophie Germain prime | A prime q where 2q + 1 is also prime. | 11 is one because 2 × 11 + 1 = 23. |
| Safe prime | The larger prime p made from p = 2q + 1. | 23 is safe because (23 − 1) / 2 = 11. |
Math Note
If q is a Sophie Germain prime, then 2q + 1 is a safe prime. If p is a safe prime, then (p − 1) / 2 is a Sophie Germain prime.
How to Tell Whether a Prime Is Safe
A prime number is not automatically safe. For example, 13 is prime, but (13 − 1) / 2 = 6, and 6 is composite. So 13 is prime, but it is not a safe prime.
Common Mistake
It is not enough for p to be prime. A safe prime must pass a second test: (p − 1) / 2 must also be prime.
| Prime p | (p − 1) / 2 | Safe Prime? |
|---|---|---|
| 13 | 6 | No, because 6 is composite. |
| 17 | 8 | No, because 8 is composite. |
| 19 | 9 | No, because 9 is composite. |
| 23 | 11 | Yes, because both 23 and 11 are prime. |
Check the Two Numbers
To test a safe prime candidate, use the prime number checker on p, then test (p − 1) / 2 separately.
Test the Two Prime Conditions
Enter p or (p − 1) / 2 and check whether each number is prime before applying the safe prime definition.
Pattern Notes for Safe Primes
Every safe prime greater than 2 is odd, because every prime greater than 2 is odd. The first safe prime is 5, not 2 or 3.
Useful Filter
Every safe prime greater than 7 has the form 12n − 1. This is only a filter, not a proof. A number can have that form and still be composite or fail the safe prime condition.
This is similar to the 6n − 1 and 6n + 1 rule for prime candidates. Such forms can narrow the search, but they do not replace a real primality test.
Why Safe Primes Matter in Number Theory
Safe primes appear in number theory because they connect two prime numbers through a simple linear formula. They also give useful examples when studying prime factorization, modular arithmetic, and the structure of multiplicative groups.
Prime Structure
A safe prime p has p − 1 = 2q, where q is also prime.
Primality Testing
Both p and q must be tested as prime numbers.
Cryptography Context
Some group-based cryptographic settings use primes with this kind of factor structure.
Safe primes are not the only primes used in cryptography, and not every cryptographic method depends on them. Their value comes from the simple factorization of p − 1 and the prime subgroup connected to q.
Related Concepts
FAQ About Safe Primes
What Is a Safe Prime?
A safe prime is a prime number p where (p − 1) / 2 is also prime. For example, 23 is a safe prime because 23 is prime and (23 − 1) / 2 = 11, which is also prime.
What Is the First Safe Prime?
The first safe prime is 5. It works because 5 is prime and (5 − 1) / 2 = 2, which is also prime.
Is Every Prime Number a Safe Prime?
No. A prime number must also have a prime value for (p − 1) / 2. For example, 13 is prime, but (13 − 1) / 2 = 6, so 13 is not a safe prime.
What Is the Difference Between a Safe Prime and a Sophie Germain Prime?
A Sophie Germain prime is the smaller prime q. The safe prime is the larger prime p = 2q + 1. For example, 11 is a Sophie Germain prime, and 23 is the matching safe prime.
Is 3 a Safe Prime?
No. Although 3 is prime, (3 − 1) / 2 = 1, and 1 is not prime. Therefore, 3 is not a safe prime.