Primality: Naïve Test

17 Dec 2021

Notes Cryptography Primality: Naïve Test

§ 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.