Motivation§

RSA is dependent on very large primes and it is not practical to have a lookup table of very large primes, so we must find a way to generate primes. We can do this by generating a random odd number then testing if it is prime.

Naïve Test§

Naïve Test

Suppose we want to determine primality of an odd integer $n$. We can do trial division for all integers $d$ in $[3\dots \sqrt{n}]$.

  • If $d \vert n$, then we can stop and say that $n$ is composite, otherwise we continue to the next value of $d$.
  • If we have exhausted all integers in the interval, then $n$ is prime.

Complexity Discussion§

This naïve test has a time complexity of $\Theta(\sqrt{n})$, however, this does not mean it is an efficient algorithm. Consider the input to the algorithm: a number. Next, we can think of a number as a sequence of digits, and it follows that the number of elements in this sequence is $\Theta(\log n)$. There exists no polynomial $P(x)$ such that $P(\log n) \in \Theta(\sqrt{n})$, therefore, this naïve algorithm is does not run in polynomial time.

In RSA, we deal with numbers exceeding $2^{300}$, and given $\mathcal{O}(\sqrt{n})$ time complexity, we can expect about $2^{150}$ trial divisions to determine primality using this method.

For illustrative purposes, suppose that $N = \log n$, i.e. $N$ is the size of the input. If we had an $\mathcal{O}(\sqrt{N})$ time algorithm for primality, then we can expect about $\sqrt{300} \approx 17$ steps to determine if a number around $2^{300}$ is prime. This is significantly smaller than the $2^{150}$ bound from the naïve test.