6
$\begingroup$

The Miller-Rabin primality test is an algorithm for checking if number is a prime. What would be best way to test implementation of such algorithm (or any primality test in general)?

$\endgroup$
  • 2
    $\begingroup$ My intuition (I bet you can find formal tests for FIPS 140-2 or something like that): Test vectors, known composites and known primes along with known-borderline-cases. $\endgroup$ – SEJPM May 10 '16 at 20:56
  • $\begingroup$ [Rather OT:] In case you do an implementation according to a book, make sure that there are no discrepancies between you and the book author on the definition of any terms employed. $\endgroup$ – Mok-Kong Shen May 12 '16 at 10:46
6
$\begingroup$

Well, the obvious thing to do is give it a long list of integers of known primality, and see whether the algorithm reports it correctly (with it occasionally reporting a composite as "relatively-prime" not being counted as an error, as long as it reports that value as composite at least 75% of the time).

However, that simple-minded test might miss something. The Miller-Rabin test can report $n$ is "composite" because of one of two reasons:

  • Because $g^{n-1} \ne 1 \bmod n$; that is, the Fermat test fails

  • Because $g^{(n-1)/2^\ell} \bmod n$ is a nontrivial squareroot of 1

If you just throw random composites $n$ at it, then it'll run into the first reason almost all the time. Hence, it makes sense to deliberately try a value $n$ that fails for the second reason.

One set of values $n$ are known as Carmichael numbers; these are composites with $g^{n-1} = 1 \bmod n$ for all integers $g$ relatively prime to $n$; if we test a Carmichael number with no small factors, the Fermat test will almost always succeed, and so if the test fails, it'll be be the second reason.

One way of finding such Carmichael numbers is to search for prime triplets $6p+1, 12p+1, 18p+1$; if all three are prime, then $(6p+1)(12p+1)(18p+1)$ is a Carmichael number.

$\endgroup$
  • 1
    $\begingroup$ That's about as good as can be, but won't catch errors where an implementation is supposed to declare an integer as probably prime after 4 consecutive MR tests with random $g$ have found the integer probably prime, but for some reason an error makes it such that only the first test matters (e.g. because the 4 $g$ are generated from the same seed). The part of the algorithm above MR is next to impossible to test in an entirely black box scenario, AFAIK. $\endgroup$ – fgrieu May 11 '16 at 6:10
1
$\begingroup$

Find other software that does the test, then compare over the first 10^10 or more integers, then over random large numbers (both inside 64-bit range and significantly larger assuming your software does that). Try various bases.

Use the Feitsma-Galway database of all 64-bit base 2 strong pseudoprimes and make sure you produce a similar results for all those numbers (these are numbers that pass the base-2 M-R test). Of course you just want to run those numbers and see they all pass base 2 -- not try to run all composites less than 2^64!

Write a simple test for some OEIS sequences that combine bases (e.g. A056915) and see if you generate the same initial terms.

Use some test pseudoprimes that pass many bases (examples). This includes some that pass the all bases less than 53, 67, 71, 73, 101, 307, 547, 877, 1009. Verify it passes all bases up to that point, then verify it does not pass with that base.

For comparison purposes you can find another program that uses the same language and write a little test script that calls both functions and compares. I did and occasionally re-run this for my Perl software using a number of other modules. You can also (hopefully very rarely) find bugs in other published code -- ideally you could submit a bug report with patch.

You could also write out the answer and send it through md5sum or similar, or do your own checksum routine. Then use the other software and do the same. This isn't quite as efficient, and not as easy with generated random inputs, but lets you compare with almost any other software.

As others have pointed out, there are a few differences in interpretation. E.g. the test isn't defined on even numbers. Some software just ignores that so will report true for some even numbers (!), while other software does a quick pretest for evens (returning true for 2 and false for all other evens). Another gotcha is how to handle bases that are larger than the input and those that are multiples of the input. Those are especially important when considering some deterministic base sets.

Primality Testing

The previous section was specially for a Miller-Rabin implementation such as mr(n,base). Testing a full primality test is a bit harder. It gets very hard when the test is unreasonably slow, such as many AKS implementations that have little testing done if they take minutes or hours to run every tiny inputs.

  • Test the individual components separately. That includes M-R, Lucas, pre-tests, etc. Make sure those parts all work. For multi-step algorithms like AKS, make sure each step is doing the right thing (I found one that had a loop bug so it just did trial division and never ran the actual test).

  • Code review with someone else if possible. For open source this is hard to get.

  • For small inputs, compare with known inputs or some other software. I have tests that use some other sieving module written by someone else to efficiently generate lists of primes, then walk through it doing a verify that my code returns true for each prime and false for each composite. IMO it's important that this input be from a completely different source, not something you wrote.

  • There are easy deterministic tests for all 64-bit inputs. For an isprime() function, there is no reason for it to be probabilistic these days. Of course for larger inputs we typically don't use deterministic tests because of the time and coding required (the good ones are a lot faster than most people realize, but still a lot slower than something like BPSW).

  • Write a harness that generates random numbers of your chosen size (e.g. 1024-bit) and sends them through someone else's system and through yours, verifying the results match. Let this run overnight.

  • If it is for Crypto, you really ought to have it carefully reviewed by experienced people. Even then you have to live with the fear that it could still miss something important. If you don't have this niggling doubt, maybe you ought not be writing crypto software... There's a reason a generic recommendation is "don't write your own crypto software" even though we all enjoy doing it anyway.

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