5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ To answer your last question, I understand that practical RSA implementations typically use the Miller-Rabin test. $\endgroup$ – Ilmari Karonen Dec 27 '16 at 23:29
8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ @ejbs There likely is a mod-pow function already defined in your bignum library $\endgroup$ – Paŭlo Ebermann Dec 28 '16 at 9:49
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.