Skip to main content
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

It is not very difficult to find large strong primes.


The original RSA article recommended, for some vague definition of large, that

  • $p$ is a large prime,
  • $p-1$ has a large prime factor $p^-$ (as a protection against Pollard's p-1 factoring),
  • and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the cycling attack).

Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against Williams's p+1 factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's Are Strong Primes Needed for RSA?).

Modern practice (in particular, FIPS 186-4) has only kept the requirements of large $p^-$ and $p^+$, or dropped them altogether, because they do not guard against the generally faster algorithms that later emerged (ECM, GNFS..). It seems these large $p^-$ and $p^+$ requirements could remain sensible for primes less than some bound like 512-bit, or/and multiprime RSA, but only when an adversary would be content with factoring one of extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).

Finding such strong RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. A basic method is to first choose $p^-$ and $p^+$ randomly, of the desired order of magnitude; then search odd $p$ with $p\equiv1\pmod{p^-}$ and $p\equiv-1\pmod{p^+}$. A first candidate is found using the Chinese Remainder Theorem, and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.

It is not very difficult to find large strong primes.


The original RSA article recommended, for some vague definition of large, that

  • $p$ is a large prime,
  • $p-1$ has a large prime factor $p^-$ (as a protection against Pollard's p-1 factoring),
  • and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the cycling attack).

Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against Williams's p+1 factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's Are Strong Primes Needed for RSA?).

Modern practice (in particular, FIPS 186-4) has only kept the requirements of large $p^-$ and $p^+$, or dropped them altogether, because they do not guard against the generally faster algorithms that later emerged (ECM, GNFS..). It seems these large $p^-$ and $p^+$ requirements could remain sensible for primes less than some bound like 512-bit, or/and multiprime RSA, but only when an adversary would be content with factoring one of extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).

Finding such strong RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. A basic method is to first choose $p^-$ and $p^+$ randomly, of the desired order of magnitude; then search odd $p$ with $p\equiv1\pmod{p^-}$ and $p\equiv-1\pmod{p^+}$. A first candidate is found using the Chinese Remainder Theorem, and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.

It is not very difficult to find large strong primes.


The original RSA article recommended, for some vague definition of large, that

  • $p$ is a large prime,
  • $p-1$ has a large prime factor $p^-$ (as a protection against Pollard's p-1 factoring),
  • and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the cycling attack).

Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against Williams's p+1 factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's Are Strong Primes Needed for RSA?).

Modern practice (in particular, FIPS 186-4) has only kept the requirements of large $p^-$ and $p^+$, or dropped them altogether because they do not guard against the generally faster algorithms that later emerged (ECM, GNFS..). It seems these large $p^-$ and $p^+$ requirements remain sensible for primes less than some bound like 512-bit, or/and multiprime RSA, but only when an adversary would be content with factoring one of extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).

Finding such strong RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. A basic method is to first choose $p^-$ and $p^+$ randomly, of the desired order of magnitude; then search odd $p$ with $p\equiv1\pmod{p^-}$ and $p\equiv-1\pmod{p^+}$. A first candidate is found using the Chinese Remainder Theorem, and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.

Post Undeleted by fgrieu
Ouups
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

It is not very difficult to find large strong primes, for whatever usual definition of that is used.


The standard definition of strong prime (OEIS A005385) is that $p=2q+1$ with $p$ and $q$ prime. The $q$ are called Sophie Germain primes (OEIS A005384).

That definition is used when we want a prime $p$ for which there is a generator $g$ of $\Bbb Z_p^*$, or of prime order $q=(p-1)/2$.

About one integer out of $(\log(n))^2$ near $n$ is a safe prime per that definition, and we are expected to find a 1024-bit safe prime by sieving an interval of about $2^{19}$ integers. Further, all safe primes above $11$ verify $p\bmod12=11$ and $p\bmod5\in\{2,3,4\}$; that reduces the number of candidates by a factor of $20$. Testing with each small prime $s$ removes a proportion $2/s$ of candidates.

After sieving with small primes, we'll do an Euler test to base $2$ for $p$, that is check $(2^q\bmod p)\in\{1,p-1\}$; and a Rabin-Miller test for $q$. It is not necessary to further test $p$: by Pocklington's theorem, if the Euler test passed, $p$ is prime if $q$ is prime and $p\equiv11\pmod{12}$.

Note: For a strong prime with $p\bmod24=11$, $g=2$ is a generator, and the Euler test for $p$ simplifies to $2^q\bmod p=p-1$. For a strong prime with $p\bmod24=23$, $g=2$ has prime order $q$, the Euler test for $p$ simplifies to $2^q\bmod p=1$, and each strong pseudoprime test in the Rabin-Miller test for $q$ simplifies to an Euler test.


In an RSA context, the approriate definition of "strong prime" is different, and varies. Actually "strong prime" is now seldom used, or perhaps is by accident. A better name is safe (RSA) prime.

The original RSA article recommended, for some vague definition of large, that

  • $p$ is a large prime,
  • $p-1$ has a large prime factor $p^-$ (as a protection against Pollard's p-1 factoring),
  • and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the cycling attack).

Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against Williams's p+1 factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's Are Strong Primes Needed for RSA?).

Modern practice (in particular, FIPS 186-4) has only kept the requirements of large $p^-$ and $p^+$, or dropped them altogether, because they do not guard against the generally faster algorithms that later emerged (ECM, GNFS..). It seems these large $p^-$ and $p^+$ requirements could remain sensible for primes less than some bound like 512-bit, or/and multiprime RSA, but only when an adversary would be content with factoring one of extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).

Finding such safestrong RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. A basic method is to first choose $p^-$ and $p^+$ randomly, of the desired order of magnitude; then search odd $p$ with $p\equiv1\pmod{p^-}$ and $p\equiv-1\pmod{p^+}$. A first candidate is found using the Chinese Remainder Theorem, and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.

It is not very difficult to find large strong primes, for whatever usual definition of that is used.


The standard definition of strong prime (OEIS A005385) is that $p=2q+1$ with $p$ and $q$ prime. The $q$ are called Sophie Germain primes (OEIS A005384).

That definition is used when we want a prime $p$ for which there is a generator $g$ of $\Bbb Z_p^*$, or of prime order $q=(p-1)/2$.

About one integer out of $(\log(n))^2$ near $n$ is a safe prime per that definition, and we are expected to find a 1024-bit safe prime by sieving an interval of about $2^{19}$ integers. Further, all safe primes above $11$ verify $p\bmod12=11$ and $p\bmod5\in\{2,3,4\}$; that reduces the number of candidates by a factor of $20$. Testing with each small prime $s$ removes a proportion $2/s$ of candidates.

After sieving with small primes, we'll do an Euler test to base $2$ for $p$, that is check $(2^q\bmod p)\in\{1,p-1\}$; and a Rabin-Miller test for $q$. It is not necessary to further test $p$: by Pocklington's theorem, if the Euler test passed, $p$ is prime if $q$ is prime and $p\equiv11\pmod{12}$.

Note: For a strong prime with $p\bmod24=11$, $g=2$ is a generator, and the Euler test for $p$ simplifies to $2^q\bmod p=p-1$. For a strong prime with $p\bmod24=23$, $g=2$ has prime order $q$, the Euler test for $p$ simplifies to $2^q\bmod p=1$, and each strong pseudoprime test in the Rabin-Miller test for $q$ simplifies to an Euler test.


In an RSA context, the approriate definition of "strong prime" is different, and varies. Actually "strong prime" is now seldom used, or perhaps is by accident. A better name is safe (RSA) prime.

The original RSA article recommended, for some vague definition of large, that

  • $p$ is a large prime,
  • $p-1$ has a large prime factor $p^-$ (as a protection against Pollard's p-1 factoring),
  • and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the cycling attack).

Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against Williams's p+1 factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's Are Strong Primes Needed for RSA?).

Modern practice (in particular, FIPS 186-4) has only kept the requirements of large $p^-$ and $p^+$, or dropped them altogether, because they do not guard against the generally faster algorithms that later emerged (ECM, GNFS..). It seems these large $p^-$ and $p^+$ requirements could remain sensible for primes less than some bound like 512-bit, or/and multiprime RSA, but only when an adversary would be content with factoring one of extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).

Finding such safe RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. A basic method is to first choose $p^-$ and $p^+$ randomly, of the desired order of magnitude; then search odd $p$ with $p\equiv1\pmod{p^-}$ and $p\equiv-1\pmod{p^+}$. A first candidate is found using the Chinese Remainder Theorem, and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.

It is not very difficult to find large strong primes.


The original RSA article recommended, for some vague definition of large, that

  • $p$ is a large prime,
  • $p-1$ has a large prime factor $p^-$ (as a protection against Pollard's p-1 factoring),
  • and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the cycling attack).

Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against Williams's p+1 factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's Are Strong Primes Needed for RSA?).

Modern practice (in particular, FIPS 186-4) has only kept the requirements of large $p^-$ and $p^+$, or dropped them altogether, because they do not guard against the generally faster algorithms that later emerged (ECM, GNFS..). It seems these large $p^-$ and $p^+$ requirements could remain sensible for primes less than some bound like 512-bit, or/and multiprime RSA, but only when an adversary would be content with factoring one of extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).

Finding such strong RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. A basic method is to first choose $p^-$ and $p^+$ randomly, of the desired order of magnitude; then search odd $p$ with $p\equiv1\pmod{p^-}$ and $p\equiv-1\pmod{p^+}$. A first candidate is found using the Chinese Remainder Theorem, and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.

Post Deleted by fgrieu
Missing words
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

It is not very difficult to find large strong primes, for whatever usual definition of that is used.


The standard definition of strong prime (OEIS A005385) is that $p=2q+1$ with $p$ and $q$ prime. The $q$ are called Sophie Germain primes (OEIS A005384).

That definition is used when we want a prime $p$ for which there is a generator $g$ of $\Bbb Z_p^*$, or of prime order $q=(p-1)/2$.

About one integer out of $(\log(n))^2$ near $n$ is a safe prime per that definition, and we are expected to find a 1024-bit safe prime by sieving an interval of about $2^{19}$ integers. Further, all safe primes above $11$ verify $p\bmod12=11$ and $p\bmod5\in\{2,3,4\}$; that reduces the number of candidates by a factor of $20$. Testing with each small prime $s$ removes a proportion $2/s$ of candidates.

After sieving with small primes, we'll do an Euler test to base $2$ for $p$, that is check $(2^q\bmod p)\in\{1,p-1\}$; and a Rabin-Miller test for $q$. It is not necessary to further test $p$: by Pocklington's theorem, if the Euler test passed, $p$ is prime if $q$ is prime and $p\equiv11\pmod{12}$.

Note: For a strong prime with $p\bmod24=11$, $g=2$ is a generator, and the Euler test for $p$ simplifies to $2^q\bmod p=p-1$. For a strong prime with $p\bmod24=23$, $g=2$ has prime order $q$, the Euler test for $p$ simplifies to $2^q\bmod p=1$, and each strong pseudoprime test in the Rabin-Miller test for $q$ simplifies to an Euler test.


In an RSA context, the approriate definition of "strong prime" is different, and varies. Actually "strong prime" is now seldom used, or perhaps is by accident. A better name is safe (RSA) prime.

The original RSA article recommended, for some vague definition of large, that

  • $p$ is a large prime,
  • $p-1$ has a large prime factor $p^-$ (as a protection against Pollard's p-1 factoring),
  • and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the cycling attack).

Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against Williams's p+1 factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's Are Strong Primes Needed for RSA?).

Modern practice (in particular, FIPS 186-4) has only kept the requirements of large $p^-$ and $p^+$, or dropped them altogether, because they do not guard against the generally faster algorithms that later emerged (ECM, GNFS..). It seems these large $p^-$ and $p^+$ requirements could remain sensible for primes less than some bound like 512-bit, or/and multiprime RSA, but only when when an adversary would be content with factoring one of extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).

Finding such safe RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. A basic method is to first choose $p^-$ and $p^+$ randomly, of the desired order of magnitude; then search odd $p$ with $p\equiv1\pmod{p^-}$ and $p\equiv-1\pmod{p^+}$. A first candidate is found using the Chinese Remainder Theorem, and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.

It is not very difficult to find large strong primes, for whatever usual definition of that is used.


The standard definition of strong prime (OEIS A005385) is that $p=2q+1$ with $p$ and $q$ prime. The $q$ are called Sophie Germain primes (OEIS A005384).

That definition is used when we want a prime $p$ for which there is a generator $g$ of $\Bbb Z_p^*$, or of prime order $q=(p-1)/2$.

About one integer out of $(\log(n))^2$ near $n$ is a safe prime per that definition, and we are expected to find a 1024-bit safe prime by sieving an interval of about $2^{19}$ integers. Further, all safe primes above $11$ verify $p\bmod12=11$ and $p\bmod5\in\{2,3,4\}$; that reduces the number of candidates by a factor of $20$. Testing with each small prime $s$ removes a proportion $2/s$ of candidates.

After sieving with small primes, we'll do an Euler test to base $2$ for $p$, that is check $(2^q\bmod p)\in\{1,p-1\}$; and a Rabin-Miller test for $q$. It is not necessary to further test $p$: by Pocklington's theorem, if the Euler test passed, $p$ is prime if $q$ is prime and $p\equiv11\pmod{12}$.

Note: For a strong prime with $p\bmod24=11$, $g=2$ is a generator, and the Euler test for $p$ simplifies to $2^q\bmod p=p-1$. For a strong prime with $p\bmod24=23$, $g=2$ has prime order $q$, the Euler test for $p$ simplifies to $2^q\bmod p=1$, and each strong pseudoprime test in the Rabin-Miller test for $q$ simplifies to an Euler test.


In an RSA context, the approriate definition of "strong prime" is different, and varies. Actually "strong prime" is now seldom used, or perhaps is by accident. A better name is safe (RSA) prime.

The original RSA article recommended, for some vague definition of large, that

  • $p$ is a large prime,
  • $p-1$ has a large prime factor $p^-$ (as a protection against Pollard's p-1 factoring),
  • and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the cycling attack).

Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against Williams's p+1 factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's Are Strong Primes Needed for RSA?).

Modern practice (in particular, FIPS 186-4) has only kept the requirements of large $p^-$ and $p^+$, or dropped them altogether, because they do not guard against the generally faster algorithms that later emerged (ECM, GNFS..). It seems these large $p^-$ and $p^+$ requirements could remain sensible for primes less than some bound like 512-bit, or/and multiprime RSA, but only when when an adversary would be content with factoring extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).

Finding such safe RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. A basic method is to first choose $p^-$ and $p^+$ randomly, of the desired order of magnitude; then search odd $p$ with $p\equiv1\pmod{p^-}$ and $p\equiv-1\pmod{p^+}$. A first candidate is found using the Chinese Remainder Theorem, and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.

It is not very difficult to find large strong primes, for whatever usual definition of that is used.


The standard definition of strong prime (OEIS A005385) is that $p=2q+1$ with $p$ and $q$ prime. The $q$ are called Sophie Germain primes (OEIS A005384).

That definition is used when we want a prime $p$ for which there is a generator $g$ of $\Bbb Z_p^*$, or of prime order $q=(p-1)/2$.

About one integer out of $(\log(n))^2$ near $n$ is a safe prime per that definition, and we are expected to find a 1024-bit safe prime by sieving an interval of about $2^{19}$ integers. Further, all safe primes above $11$ verify $p\bmod12=11$ and $p\bmod5\in\{2,3,4\}$; that reduces the number of candidates by a factor of $20$. Testing with each small prime $s$ removes a proportion $2/s$ of candidates.

After sieving with small primes, we'll do an Euler test to base $2$ for $p$, that is check $(2^q\bmod p)\in\{1,p-1\}$; and a Rabin-Miller test for $q$. It is not necessary to further test $p$: by Pocklington's theorem, if the Euler test passed, $p$ is prime if $q$ is prime and $p\equiv11\pmod{12}$.

Note: For a strong prime with $p\bmod24=11$, $g=2$ is a generator, and the Euler test for $p$ simplifies to $2^q\bmod p=p-1$. For a strong prime with $p\bmod24=23$, $g=2$ has prime order $q$, the Euler test for $p$ simplifies to $2^q\bmod p=1$, and each strong pseudoprime test in the Rabin-Miller test for $q$ simplifies to an Euler test.


In an RSA context, the approriate definition of "strong prime" is different, and varies. Actually "strong prime" is now seldom used, or perhaps is by accident. A better name is safe (RSA) prime.

The original RSA article recommended, for some vague definition of large, that

  • $p$ is a large prime,
  • $p-1$ has a large prime factor $p^-$ (as a protection against Pollard's p-1 factoring),
  • and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the cycling attack).

Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against Williams's p+1 factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's Are Strong Primes Needed for RSA?).

Modern practice (in particular, FIPS 186-4) has only kept the requirements of large $p^-$ and $p^+$, or dropped them altogether, because they do not guard against the generally faster algorithms that later emerged (ECM, GNFS..). It seems these large $p^-$ and $p^+$ requirements could remain sensible for primes less than some bound like 512-bit, or/and multiprime RSA, but only when an adversary would be content with factoring one of extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).

Finding such safe RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. A basic method is to first choose $p^-$ and $p^+$ randomly, of the desired order of magnitude; then search odd $p$ with $p\equiv1\pmod{p^-}$ and $p\equiv-1\pmod{p^+}$. A first candidate is found using the Chinese Remainder Theorem, and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.

Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Explain how we find safe RSA primes.
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Expand on how we quickly find the first kind of strong primes
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Reorganize
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading