We will actually need to have a list of prime numbers
That's dangerous, since that list must be kept secret, and primes that have been used removed to avoid reuse. There's almost always a better way, like generating the primes on demand. But let's ignore that.
My current approach here is to actually skip all the even numbers and increment the BigInteger by 2 through looping to select and filter out the possible prime numbers
If two large primes $p$ and $q$ thus obtained are used to form RSA moduli $N=p\,q$ , then that modulus $N$ will be factorable in a millisecond: compute $u=\left\lceil\sqrt N\,\right\rceil$, $v=\sqrt{u^2-N}$ (which critically will be a small integer), the factors are $u-v$ and $u+v$. That's a special case of Fermat's factorization method. This works because the two primes will be overly close¹, and illustrates a more general fact: we must generate two primes forming an RSA moduli in a way such that they bear no relationship known to an attacker².
Also, in most applications, we want that revealing the factorization of a number of $N_i$ does not help factoring any other $N_j$. For this reason, it's simplest/common/best to generate the primes independently. It remains important to generate them fast.
There are several ways to generate primes in a reasonable time. A simple one improves on the method above by avoiding not only the multiples of two, but the multiples of more small primes, so that fewer candidates will be tested before a prime is found. For example, when generating a prime with $b$ bits, we would expect to test about $b\ln(2)/2$ odd integers (that's $\approx355$ for $b=1024$), per the Prime Number Theorem. But if we manage to avoid those with no divisor among the first $127$ primes (that is, the primes to $709$), we improve this by a pleasant factor of $\displaystyle\prod_{3\le s\le709\\\,s\text{ prime}}\frac s{s-1}\ \approx5.9$.
The most usual methods towards that are
- First testing a candidate odd prime $r$ with $\gcd(r,m)=1$, where $m$ is the product of a number of small odd primes; e.g. first up to $23$, or $29$ such that $m=3234846615$ barely fits 32-bit. In one swift test, that reduces the number of prime candidates by a factor of $\approx3.17$. But if the method to test primes already does something equivalent or better, this added filtering will actually harm!
- Sieving, essentially building a sieve of Eratosthenes localized to an interval sieved. It's effective, and often practiced. But it's a tad difficult to code and optimize³; and the basic algorithm exhibits detectable bias⁴.
There are other techniques which generate provable primes, and I'm told they are competitive from a performance standpoint. See e.g. FIPS 186-4 B.3.2 for one.
I now describe an alternative to sieving, that also avoids testing candidates $r$ with a small prime factor $s$ (though to an appreciably lower bound than possible with sieving, as noted by poncho), without an explicit sieve array, and (discounting precomputations) with less work on modular reduction of a large value modulo a small prime $s$, which sometime gives a speed advantage.
In a nutshell, we'll use the Chinese Remainder Theorem to generate candidate primes $r$ with $r\bmod e$ drawn in $[2,e)$ and $r\bmod s$ drawn in $[1,s_i)$ for other small primes $s_i$.
- 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.
- 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$.
- 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$).
- 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:
- If $r<r_2$: $r\gets r+r_0$; else: $r\gets r-r_1$.
Caution: It is critical to use an unpredictable randomness source, and that all quantities manipulated remain secret.
¹ The primes will be close if they have been chosen incrementally.
² Other kinds of harmful relations between primes could be: they are generated by testing integers of the form $2\,k\,a+b$ for public $a$ and random secret $b$. That could extend to random secret $a$, if there are several $N_i$.
³ Competing computational bottlenecks are the final primality test (the more small primes are sieved, the less such tests there are), and computing the offset in the sieve (which requires computing the remainder of a large value modulo each of the small primes).
⁴ If we select the smallest prime in the sieved region, it will have a gap with the previous prime larger than expected for a random prime. Selecting a uniformly random prime in the sieved region mostly fixes that, but still the selected prime will tend to have less neighboring primes than expected for a random prime. These biases are detectable when examining the primes generated, but are not a security concern in RSA.
⁵ With $(r\bmod e)\in[2,e)$, $(r\bmod2)=1$, and $(r\bmod s_j)\in[1,s_j)$ for $0\le j<i$. The product of these distinct coprime moduli is $m$. Prime candidate $r\in[k_\min\,m,k_\max\,m)$ changes by multiples of $m$, among $t$ possible candidates. $t>2^{39.9}$, which makes it beyond reasonable doubt that there's a prime among the candidates, given the upper bound for $r_\max$. The order in which we scan them is random and secret among $>2^{39.9}$ possibilities, conjecturally defeating statistical tests of non uniformity.
⁶ This is very likely, to the point of making the contrary hard to test.
⁷ In an RSA context, it is considered acceptable to restrict to primes $r\equiv3\pmod 4$. This simplifies the strong pseudoprime test to an Euler test (or otherwise said, makes the straightforward Euler test more robust). This can be obtained by $r\gets ((1-v)\,e\bmod4)\,e+v+2$ rather than $r\gets ((v+1)\bmod 2)\,e+v+2$, and $m\gets4\,e$ rather than $m\gets2\,e$ (the later occurs in two steps).
