Notes Cryptography Naïve Test

Naïve Test

17 Dec 2021

§ 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 check if an odd $n$ is prime. We can do trial division for all integers $d$ in $\{3, \dots, \lceil\sqrt{n}\rceil\}.$

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 (i.e. in the class of polynomial-time algorithms).

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 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}\ (\sim 10^{45})$ 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.