Safe prime

In number theory is a safe prime (of English safe prime ) is a prime number of the form , which must also be prim. The corresponding prime number is called the Sophie-Germain prime number . ${\displaystyle q\in \mathbb {P} }$ ${\displaystyle q=2p+1}$ ${\displaystyle p\in \mathbb {P} }$ ${\displaystyle p}$

Naming

These primes are called "sure" because they are related to strong primes . Strong prime numbers are prime numbers if (in their cryptological definition) both and have “large” prime factors (in the sense of “a prime factor cannot be much larger than half as large as the number itself”). For safe prime numbers , the number has the large prime factor , which is why the safe prime number meets at least one criterion for strong prime numbers. ${\displaystyle q\in \mathbb {N} }$ ${\displaystyle q-1}$ ${\displaystyle q+1}$ ${\displaystyle q=2p+1}$ ${\displaystyle q-1=2p}$ ${\displaystyle p}$ ${\displaystyle q}$

The duration of methods that factor numbers that have as a prime factor depends in part on the size of the prime factor of , for example in the Pollard p-1 method . ${\displaystyle q}$ ${\displaystyle q-1}$

Secure prime numbers also play an important role in cryptology .

Examples

The smallest safe prime numbers are the following:

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, 2027, 2039, 2063, 2099, 2207, 2447, 2459, 2579, 2819, 2879, 2903, ... (series A005385 in OEIS )

The following list shows the 10 largest known safe prime numbers. All discoverers of these prime numbers are participants in the PrimeGrid project.

rank	Rank in list of prime numbers a	Prime number ${\displaystyle p}$	Decimal places of ${\displaystyle p}$	Discovery date	Explorer	source
1	1750.	${\displaystyle 2618163402417\cdot 2^{1290001}-1}$	${\displaystyle 388342}$	February 29, 2016	Scott Brown ( USA )
2	1831.	${\displaystyle 18543637900515\cdot 2^{666668}-1}$	${\displaystyle 200701}$	April 4th or 9th 2012	Lee Blyth ( AUS )
3	1851.	${\displaystyle 183027\cdot 2^{265441}-1}$	${\displaystyle 79911}$	March 22, 2010	Tom Wu
4th	1854.	${\displaystyle 648621027630345\cdot 2^{253825}-1}$	${\displaystyle 76424}$	November 18, 2009	Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai
5	1855.	${\displaystyle 620366307356565\cdot 2^{253825}-1}$	${\displaystyle 76424}$	November 2, 2009	Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai
6th	1871.	${\displaystyle 99064503957\cdot 2^{200009}-1}$	${\displaystyle 60220}$	April 1, 2016	S. Urushihata
7th	1885.	${\displaystyle 607095\cdot 2^{176312}-1}$	${\displaystyle 53081}$	September 18, 2009	Tom Wu
8th	1892.	${\displaystyle 48047305725\cdot 2^{172404}-1}$	${\displaystyle 51910}$	January 25, 2007	David Underbakke
9	1894.	${\displaystyle 137211941292195\cdot 2^{171961}-1}$	${\displaystyle 51780}$	May 3, 2006	Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai
10	1926.	${\displaystyle 21195711\cdot 2^{143630}-1}$	${\displaystyle 43245}$	June 14, 2019	Serge Batalov

^aStatus: August 13, 2019; the rank only reveals where these prime numbers are in this list

properties

• With the exception of the safe prime number , all safe prime numbers are of the form with an integer . ${\displaystyle q=7}$ ${\displaystyle q=6k+5}$ ${\displaystyle k\in \mathbb {N} }$

In other words . ${\displaystyle q\equiv 5{\pmod {6}}}$

Proof:

All numbers of the remainder classes or or are even and therefore divisible by. ${\displaystyle n\equiv 0{\pmod {6}}}$ ${\displaystyle n\equiv 2{\pmod {6}}}$ ${\displaystyle n\equiv 4{\pmod {6}}}$ ${\displaystyle 2}$

The Sophie-Germain prime leads to the secure prime number and this fulfills the condition . ${\displaystyle p=2}$ ${\displaystyle q=2\cdot 2+1=5}$ ${\displaystyle q\equiv 5{\pmod {6}}}$

All numbers of the remainder classes or are divisible by. ${\displaystyle n\equiv 0{\pmod {6}}}$ ${\displaystyle n\equiv 3{\pmod {6}}}$ ${\displaystyle 3}$

The Sophie-Germain prime number leads to the secure prime number and this does not meet the condition , but is excluded from this assertion anyway. ${\displaystyle p=3}$ ${\displaystyle q=2\cdot 3+1=7}$ ${\displaystyle q\equiv 5{\pmod {6}}}$

There are prime numbers in the remainder class , but because of this one would get secure “prime numbers” that are divisible by and therefore cannot be prime numbers. ${\displaystyle p\equiv 1{\pmod {6}}}$ ${\displaystyle q=2p+1=2\cdot (6n+1)+1=12n+3=3\cdot (4n+1)}$ ${\displaystyle 3}$

The only remaining class of six for certain prime numbers is the remainder of the class . ${\displaystyle q}$ ${\displaystyle q\equiv 5{\pmod {6}}}$ ${\displaystyle \Box }$

• With the exception of the safe prime number , all safe prime numbers are of the form with an integer . ${\displaystyle q=5}$ ${\displaystyle q=4k+3}$ ${\displaystyle k\in \mathbb {N} }$

In other words . ${\displaystyle q\equiv 3{\pmod {4}}}$

Proof:

With the exception of the first Sophie-Germain prime number (which leads to the secure prime number and for which this assertion is not true) all other prime numbers are odd, i.e. have the form with . Every sure prime number thus has the form of what was to be shown. ${\displaystyle p=2}$ ${\displaystyle q=2\cdot 2+1=5}$ ${\displaystyle p=2n+1}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle q=2p+1=2(2n+1)+1=4n+3}$ ${\displaystyle \Box }$

• With the exception of safe prime numbers and , all safe prime numbers are in the form of an integer . ${\displaystyle q=5}$ ${\displaystyle q=7}$ ${\displaystyle q=12k+11}$ ${\displaystyle k\in \mathbb {N} }$

In other words . ${\displaystyle q\equiv 11{\pmod {12}}}$

Proof:

All Sophie Germain primes lead to the secure prime numbers and have the form (see proof ). Thus what was to be shown applies to the certain prime number . ${\displaystyle p>3}$ ${\displaystyle q=2p+1>2\cdot 3+1=7}$ ${\displaystyle p=6k+5}$ ${\displaystyle q=2p+1=2\cdot (6k+5)+1=12k+11}$ ${\displaystyle \Box }$

• The following applies to all safe prime numbers : ${\displaystyle q>7}$

${\displaystyle 3}$is a quadratic remainder modulo . ${\displaystyle q}$

Proof:

Safe prime numbers have the form with . Because of the premise is . But (odd) prime numbers satisfy the congruence or , because all odd numbers of the form are divisible by. Prime numbers of the form cannot be Sophie-Germain prime numbers , because then they would be divisible by and are therefore not secure prime numbers. It just remains, so is or . Thus in both cases . But there is the mathematical theorem that a quadratic residue modulo is exactly when or is. Thus a quadratic remainder is modulo what was to be shown. ${\displaystyle q=2p+1}$ ${\displaystyle p\in \mathbb {P} }$ ${\displaystyle q>7=2p+1}$ ${\displaystyle p>3}$ ${\displaystyle p>3}$ ${\displaystyle p\equiv 1{\pmod {6}}}$ ${\displaystyle p\equiv 5{\pmod {6}}}$ ${\displaystyle n\equiv 3{\pmod {6}}}$ ${\displaystyle 3}$ ${\displaystyle p\equiv 1{\pmod {6}}}$ ${\displaystyle q=2p+1\equiv 2\cdot 1+1=3{\pmod {6}}}$ ${\displaystyle 3}$ ${\displaystyle p\equiv 5{\pmod {6}}}$ ${\displaystyle p\equiv 5{\pmod {12}}}$ ${\displaystyle p\equiv 5+6=11{\pmod {12}}}$ ${\displaystyle q=2p+1\equiv 2\cdot 5+1\equiv 2\cdot 11+1=23\equiv 11{\pmod {12}}}$ ${\displaystyle 3}$ ${\displaystyle q}$ ${\displaystyle q\equiv 1{\pmod {12}}}$ ${\displaystyle q\equiv -1\equiv 11{\pmod {12}}}$ ${\displaystyle 3}$ ${\displaystyle q}$ ${\displaystyle \Box }$

• The following applies to all safe prime numbers : ${\displaystyle q>7}$

${\displaystyle q}$shares . ${\displaystyle 3^{\frac {q-1}{2}}-1}$

Proof:

Because a quadratic residue modulo is valid following congruence : . It follows directly from this that is is a factor of . ${\displaystyle 3}$ ${\displaystyle q}$ ${\displaystyle 3^{\frac {q-1}{2}}\equiv 1{\pmod {q}}}$ ${\displaystyle q}$ ${\displaystyle 3^{\frac {q-1}{2}}-1}$ ${\displaystyle \Box }$

• Be a safe prime number. Then: ${\displaystyle q\equiv 7{\pmod {8}}}$

${\displaystyle q}$is a divisor of that Mersenne number whose exponent is the corresponding Sophie-Germain prime number.

In other words, shares with ${\displaystyle q}$ ${\displaystyle M_{p}}$ ${\displaystyle p={\frac {q-1}{2}}}$

(see also divisibility properties of the Mersenne numbers )

Example:

It is . Then the corresponding Sophie Germain prime number is . ${\displaystyle q=23\equiv 7{\pmod {8}}}$ ${\displaystyle p={\frac {23-1}{2}}=11}$

In fact is divisor of . ${\displaystyle q=23}$ ${\displaystyle M_{11}=2^{11}-1=2048-1=2047=23\cdot 89}$

• With the exception of the prime number, there are no Fermat prime numbers , which are also secure prime numbers. ${\displaystyle q=5}$

Proof:

Fermat primes are of the form . It follows that a power of two, but not a (Sophie-Germain) prime number (except for and thus for ). Thus the Fermat prime number can not be a certain number, which was to be proven. ${\displaystyle F=q=2^{n}+1}$ ${\displaystyle {\frac {F-1}{2}}={\frac {q-1}{2}}=p=2^{n-1}}$ ${\displaystyle p=2^{1}}$ ${\displaystyle q=2\cdot 2+1=5}$ ${\displaystyle F}$ ${\displaystyle \Box }$

• With the exception of the prime number, there are no Mersenne prime numbers , which are also secure prime numbers. ${\displaystyle q=7}$

Proof:

It was shown above that all safe prime numbers except for have the form . Mersenne primes are of the form . So would have to be and therefore would be . but is never divisible by, from which it follows that a Mersenne prime may never be a certain prime number at the same time (with the exception of ). ${\displaystyle q=7}$ ${\displaystyle q=6k_{2}+5=6(k_{2}+1)-1=:6k-1}$ ${\displaystyle p=2^{m}-1}$ ${\displaystyle 2^{m}-1=6k-1}$ ${\displaystyle 2^{m}=6k}$ ${\displaystyle 2^{m}}$ ${\displaystyle 6}$ ${\displaystyle q=7=2^{3}-1}$ ${\displaystyle \Box }$

• Every member of a Cunningham chain of the first kind, with the exception of the first member of such a chain, is a sure prime number.

Proof:

The proof lies in the definition of such Cunningham chains: (i.e. a Sophie-Germain prime number), all further members of the sequence have the form and are therefore safe prime numbers according to the definition. ${\displaystyle a_{0}=p}$ ${\displaystyle a_{n+1}=2\cdot a_{n}+1}$ ${\displaystyle \Box }$

• Let be a sure prime number of the form (it should end with ) which occurs in a Cunningham chain. Then: ${\displaystyle q}$ ${\displaystyle q=10k+7}$ ${\displaystyle 7}$

The number ends the Cunningham chain, so it is the last link in the chain. ${\displaystyle q}$

Proof:

The next link in this chain would be and would therefore be divisible by and therefore no longer a prime number. ${\displaystyle 2\cdot (10k+7)+1=20k+15=5\cdot (4k+3)}$ ${\displaystyle 5}$ ${\displaystyle \Box }$

• Be a prime number. Then: ${\displaystyle p\in \mathbb {P} }$

Is , then: ${\displaystyle p\equiv 1{\pmod {4}}}$

${\displaystyle q=2p+1}$is a safe prime iff divides is ${\displaystyle q=2p+1}$ ${\displaystyle 2^{p}+1}$

Is , then: ${\displaystyle p\equiv 3{\pmod {4}}}$

${\displaystyle q=2p+1}$is a safe prime iff divides is ${\displaystyle q=2p+1}$ ${\displaystyle 2^{p}-1}$

Web links

• Eric W. Weisstein : Sophie Germain Prime . In: MathWorld (English).
• Safe Prime . In: PlanetMath . (English)

Individual evidence

1. ↑ Safe Prime . In: PlanetMath . (English)
2. ↑ Chris K. Caldwell: The Top Twenty: Sophie Germain (p). Prime Pages, accessed June 24, 2018 . 
3. ↑ List of the largest known prime numbers. Retrieved June 21, 2018 . 
4. ↑ Sophie-Germain-Zahl 2618163402417 · 2 ^1290001 - 1 on Prime Pages
5. ↑ Sophie-Germain-Zahl 18543637900515 · 2 ⁶⁶⁶⁶⁶⁸ - 1 on Prime Pages
6. ↑ Sophie Germain Number 183027 · 2 ²⁶⁵⁴⁴¹ - 1 on Prime Pages
7. ↑ Sophie-Germain-Number 648621027630345 · 2 ²⁵³⁸²⁵ - 1 on Prime Pages
8. ↑ Sophie-Germain-Number 620366307356565 · 2 ²⁵³⁸²⁵ - 1 on Prime Pages
9. ↑ Sophie-Germain-Zahl 99064503957 · 2 ²⁰⁰⁰⁰⁹ - 1 on Prime Pages
10. ↑ Sophie Germain Number 607095 · 2 ^{one hundred and seventy-six thousand three hundred twelve} - 1 on Prime Pages
11. ↑ Sophie Germain Number 48047305725 · 2 ¹⁷²⁴⁰⁴ - 1 on Prime Pages
12. ↑ Sophie-Germain-Zahl 137211941292195 · 2 ¹⁷¹⁹⁶⁰ - 1 on Prime Pages
13. ↑ Sophie Germain Number 21195711 · 2 ¹⁴³⁶³⁰ - 1 on Prime Pages
14. ↑ Dušan Djukić: Quadratic Congruences. Theorem 10c. The IMO Compendium Group, 2007, pp. 1–12 , accessed March 17, 2020 . 
15. ↑ Chris K. Caldwell: Proof of a result of Euler and Lagrange on Mersenne Divisors. Prime Pages, accessed August 14, 2019 . 
16. ^ Henri Lifchitz: Generalization of Euler-Lagrange theorem and new primality tests. Retrieved August 14, 2019 .