How do you make Fermat's primality test go fast?

Question

This small Lisp-function implements Fermat's primality test in a very simple way and it is very slow at $n >= 10^6$ because we reach into bignum territory.

(defun prime-p (n)
  (= 1 (mod (expt 5 (1- n)) n)))

What am I missing? I assume that this is not the form that is actually used in implementations of RSA to find appropriate primes, what is actually used?

Answer 1

I'm not very good at reading Lisp, so please correct me if I'm wrong, but it looks as if you're naïvely calculating $a^{n-1} \bmod n$ by first raising $a$ to the $n-1$ -th power, and then reducing the result modulo $n$.

This is a very inefficient way to implement modular exponentiation since, as you've noticed, the intermediate result $a^{n-1}$ can quickly grow to an enormous size. It is far more efficient to reduce any intermediate results modulo $n$ while raising $a$ to the $n-1$ -th power, effectively doing the calculation directly in the ring $\mathbb Z / n \mathbb Z$ of residues modulo $n$.

Unfortunately, I don't know enough Lisp to directly suggest an efficient implementation of modular exponentiation for you, but the Wikipedia page I linked above does describe some suitable algorithms, and provides some iterative pseudocode implementations that you may be able to adapt.

Answer 2

You don't need to explicitly calculate $a^{m-1}$. Observe that $a^{2k} =(a^k)^2$ and that $a^{2k+1} = a \cdot (a^k)^2$.

This suggests a simple recursive function $\phi(k)$ to determine $a^k$ modulo $m$. First, reduce $a$ modulo $m$. Then, if $k$ is odd, return $ a \cdot \phi \left (\frac{k-1}{2} \right) \cdot \phi \left (\frac{k-1}{2} \right) $ reduced modulo $m$; if $k$ is even return $\phi \left( \frac{k}{2} \right ) \cdot \phi \left( \frac{k}{2} \right )$ reduced modulo $m$.

Answer 3

I didn't even get that you're using Lisp but I can answer some of your questions.

I am currently working on an RSA project myself and I can tell you that;

1. You could manually predefine 2 and 3 as primes, and look for primality of numbers only in the form of 6n-1 and 6n+1
2. if you use e = 3, as for your public key exponent, you can even get rid of 6n + 1 form, as the numbers in that form do not meet the requirement of gcd(3, 6n + 1 - 1) ≠ 1, for e to have a multiplicative inverse d in mod (p * q), if p and/or q is in that form. So if e = 3, check primality of numbers of the form 6n - 1, you won't even need to check gcd after that as gcd(3, 6n - 1 - 1) = 1 holds true for every integer n.

I am currently using a deterministic Miller-Rabin test for primality testing for numbers under 32-bit but in this it is suggested that Baillie-PSW is better under many circumstances. The latter seems more complex to implement, maybe it's not, I don't know.