Skip to main content
Cryptography

Return to Answer

Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
  • Repeat⁵: - If $2^{(r-1)/2}\bmod r$ is $1$ or $r-1$ (that is, $r$ pass the Euler test to base $2$): - Test if $r$ is primeprime⁶, using e.g. a small number of strong pseudoprime⁶pseudoprime⁷ tests to random base, and if so: - Output $r$ and stop. - If $r<r_2$: $r\gets r+r_0$; else: $r\gets r-r_1$.
  • Repeat⁵: - If $2^{(r-1)/2}\bmod r$ is $1$ or $r-1$ (that is, $r$ pass the Euler test to base $2$): - Test if $r$ is prime, using e.g. a small number of strong pseudoprime⁶ tests to random base, and if so: - Output $r$ and stop. - If $r<r_2$: $r\gets r+r_0$; else: $r\gets r-r_1$.
  • Repeat⁵: - If $2^{(r-1)/2}\bmod r$ is $1$ or $r-1$ (that is, $r$ pass the Euler test to base $2$): - Test if $r$ is prime⁶, using e.g. a small number of strong pseudoprime⁷ tests to random base, and if so: - Output $r$ and stop. - If $r<r_2$: $r\gets r+r_0$; else: $r\gets r-r_1$.
Fix
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
  1. Inputs:
    • We want to generate random primes in $r\in[r_\min,r_\max)$ for use as RSA modulus. We restrict to $2^{(2^6)}\le r_\min<1.01\,r_\min\le r_\max\le2^{(2^{20})}$. For $b$-bit primes intended for $2\,b$-bit RSA moduli with two factors, the customary interval is $\left[\left\lceil 2^{b-1/2}\right\rceil,2^b\right)$, which insures that the product of any two primes generated will be $2\,b$-bit.
    • We want to use some public exponent $e$, and thus need $\gcd(r-1,e)=1$. We restrict to $e$ an odd prime. Popular choices for $e$ are the five known Fermat primes, and 37.
  2. One-time precomputations:
    • $m\gets2\,e$.
    • $r\gets\left\lfloor(r_\max-r_\min)/(2^{40}\,m)\right\rfloor$.
    • $i=0$.
    • $s\gets 3$.
    • While $s<r$ (it's possible to abort earlier, e.g. when $s$ or $i$ is above some bound):
      • if $s\ne e$:
        • $s_i\gets s$ (these are primes saved for later use).
        • $c_i\gets(-m)^{-1}\bmod s$ (these are CRT coefficients for later use).
        • $m\gets m\,s$.
        • $r\gets\left\lfloor r/s\right\rfloor$.
        • $i\gets i+1$.
        • $s\gets$ the prime following $s$.
    • Slightly restrict the search interval for $r$ to $[k_\min\,m,k_\max\,m)\,\subset\,[r_\min,r_\max)$ with $k_\max-k_\min$ a prime $t\ne e$, as:
      • $k_\max\gets\left\lfloor r_\max/m\right\rfloor$.
      • $t\gets\left\lfloor(k_\max\,m-r_\min)/m\right\rfloor$.
      • if $t$ is even: $t\gets t-1$.
      • while $t$ is not prime or $t=e$:
        • $t\gets t-2$.
        • $k_\max\gets k_\max-1$ (optional, keeps the interval centered on $[r_\min,r_\max)$ ).
      • $k_\min\gets k_\max-t$.
  3. For each prime $r$ to generate:
    • Pick a uniformly random secret $v$ in $[0,e-2)$.
    • $r\gets ((v+1)\bmod 2)\,e+v+2$; this leaves $r$ odd with $(r\bmod e)\in[2,e)$.
    • $m\gets2\,e$ ; it now holds $r\in[0,m)$.
    • For $j$ from $0$ to $i-1$:
      • Pick a uniformly random secret $v$ in $[0,s_j-1)$.
      • $r\gets r+m\,((r+v)\,c_j\bmod s_j)$$r\gets r+m\,((r+v+1)\,c_j\bmod s_j)$ ;
        this leaves $r\bmod m$ unchanged and $(r\bmod s_j)\in[1,s_j)$.
      • $m\gets m\,s_j$ ; it now holds $r\in[0,m)$.
    • Pick a uniformly random secret $v$ in $[0,t)$, determining the first $r$ tested.
    • $r\gets r+(k_\min+v)\,m$.
    • Pick a uniformly random secret $v$ in $[0,t-1)$, determining how $r$ is stepped.
    • $v\gets v+1$.
    • $r_0=v\,m$ (increment for $r$)
    • $r_1=(t-v)\,m$ (decrement for $r$)
    • $r_2=(k_\max-v)\,m$ (threshold for an increment of $r$).
  1. Inputs:
    • We want to generate random primes in $r\in[r_\min,r_\max)$ for use as RSA modulus. We restrict to $2^{(2^6)}\le r_\min<1.01\,r_\min\le r_\max\le2^{(2^{20})}$. For $b$-bit primes intended for $2\,b$-bit RSA moduli with two factors, the customary interval is $\left[\left\lceil 2^{b-1/2}\right\rceil,2^b\right)$, which insures that the product of any two primes generated will be $2\,b$-bit.
    • We want to use some public exponent $e$, and thus need $\gcd(r-1,e)=1$. We restrict to $e$ an odd prime. Popular choices for $e$ are the five known Fermat primes, and 37.
  2. One-time precomputations:
    • $m\gets2\,e$.
    • $r\gets\left\lfloor(r_\max-r_\min)/(2^{40}\,m)\right\rfloor$.
    • $i=0$.
    • $s\gets 3$.
    • While $s<r$ (it's possible to abort earlier, e.g. when $s$ or $i$ is above some bound):
      • if $s\ne e$:
        • $s_i\gets s$ (these are primes saved for later use).
        • $c_i\gets(-m)^{-1}\bmod s$ (these are CRT coefficients for later use).
        • $m\gets m\,s$.
        • $r\gets\left\lfloor r/s\right\rfloor$.
        • $i\gets i+1$.
        • $s\gets$ the prime following $s$.
    • Slightly restrict the search interval for $r$ to $[k_\min\,m,k_\max\,m)\,\subset\,[r_\min,r_\max)$ with $k_\max-k_\min$ a prime $t\ne e$, as:
      • $k_\max\gets\left\lfloor r_\max/m\right\rfloor$.
      • $t\gets\left\lfloor(k_\max\,m-r_\min)/m\right\rfloor$.
      • if $t$ is even: $t\gets t-1$.
      • while $t$ is not prime or $t=e$:
        • $t\gets t-2$.
        • $k_\max\gets k_\max-1$ (optional, keeps the interval centered on $[r_\min,r_\max)$ ).
      • $k_\min\gets k_\max-t$.
  3. For each prime $r$ to generate:
    • Pick a uniformly random secret $v$ in $[0,e-2)$.
    • $r\gets ((v+1)\bmod 2)\,e+v+2$; this leaves $r$ odd with $(r\bmod e)\in[2,e)$.
    • $m\gets2\,e$ ; it now holds $r\in[0,m)$.
    • For $j$ from $0$ to $i-1$:
      • Pick a uniformly random secret $v$ in $[0,s_j-1)$.
      • $r\gets r+m\,((r+v)\,c_j\bmod s_j)$ ;
        this leaves $r\bmod m$ unchanged and $(r\bmod s_j)\in[1,s_j)$.
      • $m\gets m\,s_j$ ; it now holds $r\in[0,m)$.
    • Pick a uniformly random secret $v$ in $[0,t)$, determining the first $r$ tested.
    • $r\gets r+(k_\min+v)\,m$.
    • Pick a uniformly random secret $v$ in $[0,t-1)$, determining how $r$ is stepped.
    • $v\gets v+1$.
    • $r_0=v\,m$ (increment for $r$)
    • $r_1=(t-v)\,m$ (decrement for $r$)
    • $r_2=(k_\max-v)\,m$ (threshold for an increment of $r$).
  1. Inputs:
    • We want to generate random primes in $r\in[r_\min,r_\max)$ for use as RSA modulus. We restrict to $2^{(2^6)}\le r_\min<1.01\,r_\min\le r_\max\le2^{(2^{20})}$. For $b$-bit primes intended for $2\,b$-bit RSA moduli with two factors, the customary interval is $\left[\left\lceil 2^{b-1/2}\right\rceil,2^b\right)$, which insures that the product of any two primes generated will be $2\,b$-bit.
    • We want to use some public exponent $e$, and thus need $\gcd(r-1,e)=1$. We restrict to $e$ an odd prime. Popular choices for $e$ are the five known Fermat primes, and 37.
  2. One-time precomputations:
    • $m\gets2\,e$.
    • $r\gets\left\lfloor(r_\max-r_\min)/(2^{40}\,m)\right\rfloor$.
    • $i=0$.
    • $s\gets 3$.
    • While $s<r$ (it's possible to abort earlier, e.g. when $s$ or $i$ is above some bound):
      • if $s\ne e$:
        • $s_i\gets s$ (these are primes saved for later use).
        • $c_i\gets(-m)^{-1}\bmod s$ (these are CRT coefficients for later use).
        • $m\gets m\,s$.
        • $r\gets\left\lfloor r/s\right\rfloor$.
        • $i\gets i+1$.
        • $s\gets$ the prime following $s$.
    • Slightly restrict the search interval for $r$ to $[k_\min\,m,k_\max\,m)\,\subset\,[r_\min,r_\max)$ with $k_\max-k_\min$ a prime $t\ne e$, as:
      • $k_\max\gets\left\lfloor r_\max/m\right\rfloor$.
      • $t\gets\left\lfloor(k_\max\,m-r_\min)/m\right\rfloor$.
      • if $t$ is even: $t\gets t-1$.
      • while $t$ is not prime or $t=e$:
        • $t\gets t-2$.
        • $k_\max\gets k_\max-1$ (optional, keeps the interval centered on $[r_\min,r_\max)$ ).
      • $k_\min\gets k_\max-t$.
  3. For each prime $r$ to generate:
    • Pick a uniformly random secret $v$ in $[0,e-2)$.
    • $r\gets ((v+1)\bmod 2)\,e+v+2$; this leaves $r$ odd with $(r\bmod e)\in[2,e)$.
    • $m\gets2\,e$ ; it now holds $r\in[0,m)$.
    • For $j$ from $0$ to $i-1$:
      • Pick a uniformly random secret $v$ in $[0,s_j-1)$.
      • $r\gets r+m\,((r+v+1)\,c_j\bmod s_j)$ ;
        this leaves $r\bmod m$ unchanged and $(r\bmod s_j)\in[1,s_j)$.
      • $m\gets m\,s_j$ ; it now holds $r\in[0,m)$.
    • Pick a uniformly random secret $v$ in $[0,t)$, determining the first $r$ tested.
    • $r\gets r+(k_\min+v)\,m$.
    • Pick a uniformly random secret $v$ in $[0,t-1)$, determining how $r$ is stepped.
    • $v\gets v+1$.
    • $r_0=v\,m$ (increment for $r$)
    • $r_1=(t-v)\,m$ (decrement for $r$)
    • $r_2=(k_\max-v)\,m$ (threshold for an increment of $r$).
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
  1. Inputs:
    • We want to generate random primes in $r\in[r_\min,r_\max)$ for use as RSA modulus. We restrict to $2^{(2^6)}\le r_\min<1.01\,r_\min\le r_\max\le2^{(2^{20})}$. For $b$-bit primes intended for $2\,b$-bit RSA moduli with two factors, the customary interval is $\left[\left\lceil 2^{b-1/2}\right\rceil,2^b\right)$, which insures that the product of any two primes generated will be $2\,b$-bit.
    • We want to use some public exponent $e$, and thus need $\gcd(r-1,e)=1$. We restrict to $e$ an odd prime. Popular choices for $e$ are the five known Fermat primes, and 37.
  2. One-time precomputations:
    • $m\gets2\,e$.
    • $r\gets\left\lfloor(r_\max-r_\min)/(2^{40}\,m)\right\rfloor$.
    • $i=0$.
    • $s\gets 3$.
    • While $s<r$ (it's possible to abort earlier, e.g. when $s$ or $i$ is above some bound):
      • if $s\ne e$:
        • $s_i\gets s$ (these are primes saved for later use).
        • $c_i\gets(-m)^{-1}\bmod s$ (these are CRT coefficients for later use).
        • $m\gets m\,s$.
        • $r\gets\left\lfloor r/s\right\rfloor$.
        • $i\gets i+1$.
        • $s\gets$ the prime following $s$.
    • Slightly restrict the search interval for $r$ to $[k_\min\,m,k_\max\,m)\,\subset\,[r_\min,r_\max)$ with $k_\max-k_\min$ a prime $t\ne e$, as:
      • $k_\max\gets\left\lfloor r_\max/m\right\rfloor$.
      • $t\gets\left\lfloor(k_\max\,m-r_\min)/m\right\rfloor$.
      • if $t$ is even: $t\gets t-1$.
      • while $t$ is not prime or $t=e$:
        • $t\gets t-2$.
        • $k_\max\gets k_\max-1$ (optional, keeps the interval centered on $[r_\min,r_\max)$ ).
      • $k_\min\gets k_\max-t$.
  3. For each prime $r$ to generate:
    • Pick a uniformly random secret $v$ in $[0,e-2)$.
    • $r\gets ((v+1)\bmod 2)\,e+v+2$; this leaves $r$ odd with $(r\bmod e)\in[2,e)$.
    • $m\gets2\,e$ ; it now holds $r\in[0,m)$.
    • For $j$ from $0$ to $i-1$:
      • Pick a uniformly random secret $v$ in $[0,s_j-1)$.
      • $r\gets r+m\,((r+v)\,c_j\bmod s_j)$ ;
        this leaves $r\bmod m$ unchanged and $(r\bmod s_j)\in[1,s_j)$.
      • $m\gets m\,s_j$ ; it now holds $r\in[0,m)$.
    • Pick a uniformly random secret $v$ in $[0,t)$, determining the first $r$ tested.
    • $r\gets r+(k_\min+v)\,m$.
    • Pick a uniformly random secret $v$ in $[0,t-1)$, determining how $r$ is stepped.
    • $v\gets v+1$.
    • $r_0=v\,m$ (increment for $r$)
    • $r_1=(t-v)\,m$ (decrement offor $r$)
    • $r_2=(k_\max-v)\,m$ (threshold for an increment of $r$).
  • Repeat⁵: - If $2^{(r-1)/2}\bmod r$ is $1$ or $r-1$ (that is, $r$ pass the Euler test to base $2$): - Test if $r$ is prime, using e.g. a small number of strong pseudoprime⁶ tests to random base, and if so: - Output $r$ and stop. - If $r<r_2$: $r\gets r+r_0$. -; else: $r\gets r-r_1$.
  1. Inputs:
    • We want to generate random primes in $r\in[r_\min,r_\max)$ for use as RSA modulus. We restrict to $2^{(2^6)}\le r_\min<1.01\,r_\min\le r_\max\le2^{(2^{20})}$. For $b$-bit primes intended for $2\,b$-bit RSA moduli with two factors, the customary interval is $\left[\left\lceil 2^{b-1/2}\right\rceil,2^b\right)$, which insures that the product of any two primes generated will be $2\,b$-bit.
    • We want to use some public exponent $e$, and thus need $\gcd(r-1,e)=1$. We restrict to $e$ an odd prime. Popular choices for $e$ are the five known Fermat primes, and 37.
  2. One-time precomputations:
    • $m\gets2\,e$.
    • $r\gets\left\lfloor(r_\max-r_\min)/(2^{40}\,m)\right\rfloor$.
    • $i=0$.
    • $s\gets 3$.
    • While $s<r$ (it's possible to abort earlier, e.g. when $s$ or $i$ is above some bound):
      • if $s\ne e$:
        • $s_i\gets s$ (these are primes saved for later use).
        • $c_i\gets(-m)^{-1}\bmod s$ (these are CRT coefficients for later use).
        • $m\gets m\,s$.
        • $r\gets\left\lfloor r/s\right\rfloor$.
        • $i\gets i+1$.
        • $s\gets$ the prime following $s$.
    • Slightly restrict the search interval for $r$ to $[k_\min\,m,k_\max\,m)\,\subset\,[r_\min,r_\max)$ with $k_\max-k_\min$ a prime $t\ne e$, as:
      • $k_\max\gets\left\lfloor r_\max/m\right\rfloor$.
      • $t\gets\left\lfloor(k_\max\,m-r_\min)/m\right\rfloor$.
      • if $t$ is even: $t\gets t-1$.
      • while $t$ is not prime or $t=e$:
        • $t\gets t-2$.
        • $k_\max\gets k_\max-1$ (optional, keeps the interval centered on $[r_\min,r_\max)$ ).
      • $k_\min\gets k_\max-t$.
  3. For each prime $r$ to generate:
    • Pick a uniformly random secret $v$ in $[0,e-2)$.
    • $r\gets ((v+1)\bmod 2)\,e+v+2$; this leaves $r$ odd with $(r\bmod e)\in[2,e)$.
    • $m\gets2\,e$ ; it now holds $r\in[0,m)$.
    • For $j$ from $0$ to $i-1$:
      • Pick a uniformly random secret $v$ in $[0,s_j-1)$.
      • $r\gets r+m\,((r+v)\,c_j\bmod s_j)$ ;
        this leaves $r\bmod m$ unchanged and $(r\bmod s_j)\in[1,s_j)$.
      • $m\gets m\,s_j$ ; it now holds $r\in[0,m)$.
    • Pick a uniformly random secret $v$ in $[0,t)$, determining the first $r$ tested.
    • $r\gets r+(k_\min+v)\,m$.
    • Pick a uniformly random secret $v$ in $[0,t-1)$, determining how $r$ is stepped.
    • $v\gets v+1$.
    • $r_0=v\,m$ (increment for $r$)
    • $r_1=(t-v)\,m$ (decrement of $r$)
    • $r_2=(k_\max-v)\,m$ (threshold for an increment of $r$).
  • Repeat⁵: - If $2^{(r-1)/2}\bmod r$ is $1$ or $r-1$ (that is, $r$ pass the Euler test to base $2$): - Test if $r$ is prime, using e.g. a small number of strong pseudoprime⁶ tests to random base, and if so: - Output $r$ and stop. - If $r<r_2$: $r\gets r+r_0$. - else: $r\gets r-r_1$.
  1. Inputs:
    • We want to generate random primes in $r\in[r_\min,r_\max)$ for use as RSA modulus. We restrict to $2^{(2^6)}\le r_\min<1.01\,r_\min\le r_\max\le2^{(2^{20})}$. For $b$-bit primes intended for $2\,b$-bit RSA moduli with two factors, the customary interval is $\left[\left\lceil 2^{b-1/2}\right\rceil,2^b\right)$, which insures that the product of any two primes generated will be $2\,b$-bit.
    • We want to use some public exponent $e$, and thus need $\gcd(r-1,e)=1$. We restrict to $e$ an odd prime. Popular choices for $e$ are the five known Fermat primes, and 37.
  2. One-time precomputations:
    • $m\gets2\,e$.
    • $r\gets\left\lfloor(r_\max-r_\min)/(2^{40}\,m)\right\rfloor$.
    • $i=0$.
    • $s\gets 3$.
    • While $s<r$ (it's possible to abort earlier, e.g. when $s$ or $i$ is above some bound):
      • if $s\ne e$:
        • $s_i\gets s$ (these are primes saved for later use).
        • $c_i\gets(-m)^{-1}\bmod s$ (these are CRT coefficients for later use).
        • $m\gets m\,s$.
        • $r\gets\left\lfloor r/s\right\rfloor$.
        • $i\gets i+1$.
        • $s\gets$ the prime following $s$.
    • Slightly restrict the search interval for $r$ to $[k_\min\,m,k_\max\,m)\,\subset\,[r_\min,r_\max)$ with $k_\max-k_\min$ a prime $t\ne e$, as:
      • $k_\max\gets\left\lfloor r_\max/m\right\rfloor$.
      • $t\gets\left\lfloor(k_\max\,m-r_\min)/m\right\rfloor$.
      • if $t$ is even: $t\gets t-1$.
      • while $t$ is not prime or $t=e$:
        • $t\gets t-2$.
        • $k_\max\gets k_\max-1$ (optional, keeps the interval centered on $[r_\min,r_\max)$ ).
      • $k_\min\gets k_\max-t$.
  3. For each prime $r$ to generate:
    • Pick a uniformly random secret $v$ in $[0,e-2)$.
    • $r\gets ((v+1)\bmod 2)\,e+v+2$; this leaves $r$ odd with $(r\bmod e)\in[2,e)$.
    • $m\gets2\,e$ ; it now holds $r\in[0,m)$.
    • For $j$ from $0$ to $i-1$:
      • Pick a uniformly random secret $v$ in $[0,s_j-1)$.
      • $r\gets r+m\,((r+v)\,c_j\bmod s_j)$ ;
        this leaves $r\bmod m$ unchanged and $(r\bmod s_j)\in[1,s_j)$.
      • $m\gets m\,s_j$ ; it now holds $r\in[0,m)$.
    • Pick a uniformly random secret $v$ in $[0,t)$, determining the first $r$ tested.
    • $r\gets r+(k_\min+v)\,m$.
    • Pick a uniformly random secret $v$ in $[0,t-1)$, determining how $r$ is stepped.
    • $v\gets v+1$.
    • $r_0=v\,m$ (increment for $r$)
    • $r_1=(t-v)\,m$ (decrement for $r$)
    • $r_2=(k_\max-v)\,m$ (threshold for an increment of $r$).
  • Repeat⁵: - If $2^{(r-1)/2}\bmod r$ is $1$ or $r-1$ (that is, $r$ pass the Euler test to base $2$): - Test if $r$ is prime, using e.g. a small number of strong pseudoprime⁶ tests to random base, and if so: - Output $r$ and stop. - If $r<r_2$: $r\gets r+r_0$; else: $r\gets r-r_1$.
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Improve algorithm
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Improve algorithm
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Make it least likely that few small primes are skipped
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
Polish
Source Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611
1
2