Safe Prime Checker
Enter a positive integer to test whether it is prime and whether (p − 1) / 2 is also prime. A number passes only when both tests return prime.
Use digits only. The checker accepts integers with up to 1,000 digits and performs the calculation on this page.
What Is a Safe Prime?
A safe prime is a prime number p for which the number obtained by halving p − 1 is also prime. The definition is:
The same relationship can be written as p = 2q + 1. For example, 23 is a safe prime because 23 is prime and:
Since 11 is also prime, 23 meets both conditions. The word safe refers to the factorization p − 1 = 2q. It does not mean that every safe prime is large enough for cryptographic use.
(13 − 1) / 2 = 6, and 6 is composite.How the Checker Reaches Its Result
The input number must be prime
If p is composite, it cannot be a safe prime. This remains true even when (p − 1) / 2 happens to be prime. For example, 15 fails because 15 is composite, although (15 − 1) / 2 = 7 is prime.
The associated number must also be prime
When p is prime, the checker calculates q. If q is composite or less than 2, the input is an ordinary prime rather than a safe prime.
The result shows both parts
The result card displays the input classification, the calculated value of q, the second primality result and the final safe-prime classification. This makes a failed test easy to trace instead of returning an unexplained yes or no.
To test a number without applying the safe-prime condition, use the Prime Number Checker.
Worked Safe Prime Tests
| Input p | Is p prime? | q = (p − 1) / 2 | Is q prime? | Result |
|---|---|---|---|---|
| 5 | Yes | 2 | Yes | Safe prime |
| 7 | Yes | 3 | Yes | Safe prime |
| 23 | Yes | 11 | Yes | Safe prime |
| 13 | Yes | 6 | No | Prime, but not safe |
| 15 | No | 7 | Yes | Not a safe prime |
| 3 | Yes | 1 | No | Prime, but not safe |
Why 23 passes
The divisors of 23 are 1 and 23, so 23 is prime. Its associated value is 11, whose only positive divisors are 1 and 11. Both checks pass.
Why 13 fails
The number 13 is prime, but the second value is 6. Since 6 = 2 × 3, the safe-prime condition fails.
Why 15 fails even though 7 is prime
A safe prime needs both numbers to be prime. The second test cannot rescue a composite input. Because 15 = 3 × 5, 15 fails immediately.
Safe Primes and Sophie Germain Primes
The formula p = 2q + 1 connects two named prime classes. When both q and 2q + 1 are prime, q is called a Sophie Germain prime, while p is the corresponding safe prime.
2 × 11 + 1 = 23 is prime. The matching safe prime is 23.| Sophie Germain prime q | Calculation | Safe prime p |
|---|---|---|
| 2 | 2 × 2 + 1 | 5 |
| 3 | 2 × 3 + 1 | 7 |
| 5 | 2 × 5 + 1 | 11 |
| 11 | 2 × 11 + 1 | 23 |
| 23 | 2 × 23 + 1 | 47 |
| 29 | 2 × 29 + 1 | 59 |
| 41 | 2 × 41 + 1 | 83 |
| 53 | 2 × 53 + 1 | 107 |
The names describe opposite sides of the same equation. A Sophie Germain prime is the smaller value q; a safe prime is the larger value 2q + 1.
Useful Patterns and Fast Rejections
Number patterns can reject many candidates before a full primality test. They cannot prove that a candidate is a safe prime.
Every safe prime is odd
The smallest safe prime is 5. Since every prime greater than 2 is odd, all safe primes are odd.
Safe primes greater than 7 leave remainder 11 when divided by 12
For every safe prime p > 7:
The pattern appears in 11, 23, 47, 59, 83 and 107. It follows from the restrictions on the associated prime q. For values beyond the small exceptions, q must be congruent to 5 modulo 6, which makes 2q + 1 congruent to 11 modulo 12.
143 = 11 × 13. Both primality tests are still required.Safe primes greater than 5 are 3 modulo 4
For an odd prime q, the value 2q + 1 has remainder 3 when divided by 4. This is another useful filter, but many composite numbers share the same remainder.
First Safe Primes
The sequence begins:
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587
| Safe prime p | Associated prime q | Check |
|---|---|---|
| 5 | 2 | 5 = 2 × 2 + 1 |
| 7 | 3 | 7 = 2 × 3 + 1 |
| 11 | 5 | 11 = 2 × 5 + 1 |
| 23 | 11 | 23 = 2 × 11 + 1 |
| 47 | 23 | 47 = 2 × 23 + 1 |
| 59 | 29 | 59 = 2 × 29 + 1 |
| 83 | 41 | 83 = 2 × 41 + 1 |
| 107 | 53 | 107 = 2 × 53 + 1 |
Safe primes become less common as numbers grow because two linked expressions must both be prime. The first primality condition alone is not enough.
Why Safe Primes Appear in Cryptography
Safe primes appear in some finite-field Diffie–Hellman groups. Their useful property comes from the simple factorization:
When p and q are prime, the multiplicative group modulo p has order 2q. Its possible subgroup orders are therefore limited to 1, 2, q and 2q. This clean structure helps protocol designers choose and validate group parameters.
Standardized finite-field Diffie–Hellman parameter sets include safe-prime moduli. The checker on this page, however, classifies a number only by its mathematics. It does not generate keys, select a generator, validate a protocol implementation or decide whether a number has enough bits for a real security system.
Safe Prime, Prime and Strong Prime
| Term | Condition | Example or note |
|---|---|---|
| Prime number | Has exactly two positive divisors: 1 and itself | 13 is prime |
| Safe prime | p and (p − 1) / 2 are both prime | 23 is safe because 11 is prime |
| Sophie Germain prime | q and 2q + 1 are both prime | 11 pairs with the safe prime 23 |
| Strong prime | Uses conditions involving large prime factors near p − 1 and p + 1 | It is a different term, not a synonym for safe prime |
Every safe prime is prime, but most primes are not safe primes. The safe-prime condition adds a second linked primality test.
Exact and Probable Results
The checker uses integer arithmetic throughout. For inputs below 264, it applies a deterministic Miller–Rabin test with a base set that covers that range. A prime result in that range is exact.
For larger inputs, the checker uses multiple Miller–Rabin bases and labels a passing result as probable prime or probable safe prime. A composite result is definite because a discovered witness proves compositeness. A probable-prime result means that no tested base exposed a factor.
Input behavior
- Positive integers: accepted.
- Zero and one: not prime and therefore not safe primes.
- Negative integers: rejected by this checker.
- Decimals: rejected because primality applies to integers.
- Expressions such as 2^127 − 1: enter the expanded integer instead.
- Very long inputs: limited to 1,000 digits to keep browser calculations manageable.
Safe Prime Questions
Is 2 a safe prime?
No. Although 2 is prime, (2 − 1) / 2 = 0.5 is not an integer prime. Safe primes begin with 5.
Is 3 a safe prime?
No. The number 3 is prime, but (3 − 1) / 2 = 1. The number 1 is not prime.
Is every Sophie Germain prime a safe prime?
No. The Sophie Germain prime is the smaller number q. Its matching value 2q + 1 is the safe prime. For example, 11 is a Sophie Germain prime and 23 is its corresponding safe prime.
Can a composite number produce a prime q value?
Yes. For 15, the associated value is 7, which is prime. The input still fails because a safe prime requires p itself to be prime.
Does p mod 12 = 11 prove that p is safe?
No. It is only a filter for candidates greater than 7. The input and (p − 1) / 2 must each pass a primality test.
Why does the result sometimes say probable safe prime?
The checker gives deterministic results within its stated 64-bit range. Above that range, it uses several Miller–Rabin rounds. Passing those rounds provides strong evidence but is not presented as a formal primality proof.