Strong prime

A strong prime number (from the English strong prime ) is an integer with certain properties, which, however, differ depending on the perspective in cryptography or in number theory . ${\displaystyle p\in \mathbb {N} }$

Definition in number theory

In number theory, a strong prime number in the number-theoretical sense is an integer that is larger than the arithmetic mean of its next smaller prime number and its next larger prime number . In other words . ${\displaystyle p_{n}\in \mathbb {P} }$ ${\displaystyle p_{n-1}\in \mathbb {P} }$ ${\displaystyle p_{n+1}\in \mathbb {P} }$ ${\displaystyle p_{n}>{\frac {p_{n-1}+p_{n+1}}{2}}}$

Examples

• The prime number is the seventh prime number. The next smaller, the sixth prime, is , the next larger, the eighth prime, is . The arithmetic mean of and is . Obviously , so is a strong prime. ${\displaystyle p_{7}=17}$ ${\displaystyle p_{6}=13}$ ${\displaystyle p_{8}=19}$ ${\displaystyle p_{6}}$ ${\displaystyle p_{8}}$ ${\displaystyle {\frac {p_{6}+p_{8}}{2}}={\frac {13+19}{2}}={\frac {32}{2}}=16}$ ${\displaystyle p_{7}=17>16}$ ${\displaystyle 17}$
• The smallest strong prime numbers in the number theoretic sense are the following:

11, 17, 29, 37, 41, 59, 67, 71, 79, 97, 101, 107, 127, 137, 149, 163, 179, 191, 197, 223, 227, 239, 251, 269, 277, 281, 307, 311, 331, 347, 367, 379, 397, 419, 431, 439, 457, 461, 479, 487, 499, 521, 541, 557, 569, 587, 599, ... (sequence A051634 in OEIS )

properties

• A strong prime number in the sense of number theory is closer to the next higher prime than to the next lower prime number.

Proof:

This property results from the definition that a strong prime number must be greater than the arithmetic mean of its prime neighbors. ${\displaystyle \Box }$

• For prime twins with : is a strong prime number. ${\displaystyle (p,p+2)}$ ${\displaystyle p>5}$ ${\displaystyle p}$

Proof:

There are no prime triplets of the form because the number must divide at least one of these three numbers. If and are prime numbers, the number must divide. Thus is not prime. Thus the next lower prime of is not , but maximum . So for the arithmetic mean of the prime neighbors of , the definition for strong prime numbers is fulfilled. ${\displaystyle (p-2,p,p+2)}$ ${\displaystyle 3}$ ${\displaystyle p}$ ${\displaystyle p+2}$ ${\displaystyle 3}$ ${\displaystyle p-2}$ ${\displaystyle p-2}$ ${\displaystyle p}$ ${\displaystyle p-2}$ ${\displaystyle p-4}$ ${\displaystyle p}$ ${\displaystyle {\frac {p_{n-1}+p_{n+1}}{2}}\leq {\frac {p-4+p+2}{2}}={\frac {2p-2}{2}}=p-1<p}$ ${\displaystyle \Box }$

• The only prime twins that are not strongly prime are the pairs and (resulting from the upper property). ${\displaystyle (p,p+2)}$ ${\displaystyle p}$ ${\displaystyle (3,5)}$ ${\displaystyle (5,7)}$

Definition in cryptography

In cryptography , a strong prime number is an integer in the cryptographic sense if it fulfills the following properties: ${\displaystyle p\in \mathbb {P} }$

• ${\displaystyle p}$cannot be factored in a reasonable time using the Pollard p-1 method (but they can still be attacked, i.e. factored, using other methods such as Lenstra's elliptic curve factorization (ECM) ( s )).

In other words, a strong prime number in the cryptographic sense should meet the following conditions:

• ${\displaystyle p}$is big enough to be used in cryptography. Because of the "size" of, cryptanalysts should not be able to factor them (that is, to break them down into their prime divisors ). ${\displaystyle p}$
• ${\displaystyle p-1}$ has "large" prime factors.

That is, with and a large prime number . ${\displaystyle p-1=a_{1}\cdot q_{1}}$ ${\displaystyle a_{1}\in \mathbb {N} }$ ${\displaystyle q_{1}}$

• ${\displaystyle q_{1}-1}$ has "large" prime factors.

That is, with and a large prime number . ${\displaystyle q_{1}-1=a_{2}\cdot q_{2}}$ ${\displaystyle a_{2}\in \mathbb {N} }$ ${\displaystyle q_{2}}$

• ${\displaystyle p+1}$ has "large" prime factors.

That is, with and a large prime number . ${\displaystyle p+1=a_{3}\cdot q_{3}}$ ${\displaystyle a_{3}\in \mathbb {N} }$ ${\displaystyle q_{3}}$

Application in cryptography

When generating keys in RSA cryptosystems , the module should be used as the product of two strong prime numbers and (see Generation of the public and private key ). This method makes the factoring of the composite number thus obtained impracticable with, for example, the Pollard p-1 method . ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle n=p\cdot q}$

Example of a strong prime number in a number theoretic and cryptographic sense

There are strong prime numbers that meet both definitions, i.e. those in the number theoretical sense and those in the cryptographic sense. The following number meets both definitions:

${\displaystyle p_{n}=439351292910452432574786963588089477522344331\in \mathbb {P} }$

The next lower prime is

${\displaystyle p_{n-1}=p_{n}-132=439351292910452432574786963588089477522344199\in \mathbb {P} }$

The next larger prime is

${\displaystyle p_{n+1}=p_{n}+8=439351292910452432574786963588089477522344339\in \mathbb {P} }$

Thus applies to the arithmetic mean

${\displaystyle p_{n}>{\frac {p_{n-1}+p_{n+1}}{2}}=439351292910452432574786963588089477522344269}$

The number is larger than the arithmetic mean of its prime neighbors and thus it fulfills the number-theoretical definition of strong prime numbers. ${\displaystyle p_{n}}$ ${\displaystyle 62}$ ${\displaystyle p_{n-1}}$ ${\displaystyle p_{n+1}}$

The prime factorization of the number is: ${\displaystyle p_{n}-1}$

${\displaystyle p_{n}-1=439351292910452432574786963588089477522344330=2\cdot 5\cdot 281\cdot 3463\cdot 25831859679582977\cdot 1747822896920092227343=a_{1}\cdot q_{1}}$

It is as requested with and sufficiently large ${\displaystyle p-1=a_{1}\cdot q_{1}}$ ${\displaystyle a_{1}\in \mathbb {N} }$ ${\displaystyle q_{1}=1747822896920092227343\in \mathbb {P} }$

The prime factorization of the number is: ${\displaystyle q_{1}-1}$

${\displaystyle q_{1}-1=1747822896920092227342=2\cdot 3\cdot 173\cdot 1683837087591611009=a_{2}\cdot q_{2}}$

It is as requested with and sufficiently large ${\displaystyle q_{1}-1=a_{2}\cdot q_{2}}$ ${\displaystyle a_{2}\in \mathbb {N} }$ ${\displaystyle q_{2}=1683837087591611009\in \mathbb {P} }$

The prime factorization of the number is: ${\displaystyle p_{n}+1}$

${\displaystyle p_{n}+1=439351292910452432574786963588089477522344332=2^{2}\cdot 3^{2}\cdot 7691\cdot 352463\cdot 5207073944711\cdot 864608136454559457049=a_{3}\cdot q_{3}}$

It is as requested with and sufficiently large ${\displaystyle p+1=a_{3}\cdot q_{3}}$ ${\displaystyle a_{3}\in \mathbb {N} }$ ${\displaystyle q_{3}=864608136454559457049\in \mathbb {P} }$

The number thus also fulfills the cryptographic definition of strong prime numbers. ${\displaystyle p_{n}}$

Mind you: this prime number , which is strong in both definitions, fulfills the cryptographic definition if you allow factoring algorithms that may well be more advanced than the trial division , as long as you calculate by hand. Modern computer algebra systems factor the above numbers in fractions of a second. A currently strong prime number in the cryptographic sense ( s ) must be much larger than the above number . ${\displaystyle p_{n}}$ ${\displaystyle p_{n}}$

Designations

If you compare a prime number with the arithmetic mean of its prime neighbors and , you get the following types: ${\displaystyle p_{n}}$ ${\displaystyle {\frac {p_{n-1}+p_{n+1}}{2}}}$ ${\displaystyle p_{n-1}}$ ${\displaystyle p_{n+1}}$

• Is is called a strong prime number . ${\displaystyle p_{n}>{\frac {p_{n-1}+p_{n+1}}{2}}}$ ${\displaystyle p_{n}}$

It is closer to the next prime than to the previous prime . ${\displaystyle p_{n+1}}$ ${\displaystyle p_{n-1}}$

• Is , so one calls balanced prime (from the English balanced prime ). ${\displaystyle p_{n}={\frac {p_{n-1}+p_{n+1}}{2}}}$ ${\displaystyle p_{n}}$

It lies exactly between the next prime number and the previous prime number . ${\displaystyle p_{n+1}}$ ${\displaystyle p_{n-1}}$

• Is , so one calls a weak prime number (from the English weak prime , not to be confused with the term “ weak prime number ” (from the English weakly prime number )). ${\displaystyle p_{n}<{\frac {p_{n-1}+p_{n+1}}{2}}}$ ${\displaystyle p_{n}}$

It is closer to the previous prime than to the next prime . ${\displaystyle p_{n-1}}$ ${\displaystyle p_{n+1}}$

See also

• Safe prime

Individual evidence

1. ↑ ^{a b c} Strong Prime . In: PlanetMath . (English)
2. ^ Ron Rivest, Robert Silverman: Are 'Strong' Primes Needed for RSA. Cryptology ePrint Archive: Report 2001/007, accessed June 24, 2018 . 

Web links

• Alexander W. Dent, Chris J. Mitchell: A Companion to User's Guide to Cryptography and Standards. Retrieved May 27, 2018 . 
• Strong Prime . In: PlanetMath . (English)