Miller-Rabin test

#1

I just learned about JUCE today, so I’m having fun just exploring!

I noticed in the Miller-Rabin test for testing for pseudo-primes that the base chosen in each iteration is random. But it’s actually best for the base to be a prime, since the test is based on Fermat’s little theorem, which is applicable only for primes. Any prime works, but small primes are more efficient to use in the computation, so usually you just test in order (2, 3, 5, 7, 11, 13, 17, 19…)

Actually in practice, using random numbers as base tests won’t misidentify a prime as nonprime, though, but it does increase the probability of nonprimes to pass make the test less efficient. Using prime bases only has no drawbacks. So JUCE’s current method will still work, but it will be both slower and less likely to spot composites than a prime basis set of tests.

This page has a lot more info on using MR, especially some useful guarantees of primality for different ranges of N.
http://primes.utm.edu/prove/prove2_3.html

The JUCE test could also be tuned more with some initial GCD computations to eliminate most composites before firing up the (slow) pseudo-prime computation, but a GCD step really is optional and probably the speed of prime testing isn’t a priority for JUCE. Still, it’s easy to add something to Prime::isProbabablyPrime like:

[code]const BitArray screen (23571113171923);
BitArray GCD(findGreatestCommonDivisor(number, screen));
if (GCD != one) return false; // not prime, “number” has a small divisor.

[/code]

Forgive me if I misunderstand the JUCE code! I am just looking over it for the first time and I was instantly impressed by the clean and clear style.

#2

Thanks!

That’s interesting. I’m not any kind of crypto expert, so would have just been blindly following someone else’s algorithm when I wrote it!

…so you’re suggesting that this would work better than random numbers:

    ...
    BitArray smallPrimes;
    int numBitsInSmallPrimes = 0;
    int smallPrime = 0;

    while (--iterations >= 0)
    {
        for (;;)
        {
            const int nextIndex = smallPrimes.findNextSetBit (smallPrime);

            if (nextIndex > 0)
            {
                smallPrime = nextIndex;
                break;
            }

            numBitsInSmallPrimes += 2048;
            createSmallSieve (numBitsInSmallPrimes, smallPrimes);
        }

        BitArray r (smallPrime);
        //r.createRandomNumber (nMinusOne);
        r.exponentModulo (d, n);

?

#3

Well, your implementation was clean and clear, and the math wasn’t efficient, but it wasn’t wrong. So you’re already ahead of even most professional crypto guys who know math but can’t code properly!

I haven’t compiled and run it yet (ha, in fact I’ve never compiled JUCE, I just learned about it yesterday) but from reading the small seive code, it looks like it should work fine. You’re just computing the primes up to 2048 via a seive, using them in order, and if you run out, recomputing a larger seive.

The first pass will already give you 309 primes, which is way more than you’ll ever need even for strong crypto… your own comments recommend 20-30 tests is good for a guarantee, and that’s true in practice if you use independent primes.

I probably would have just hardwired a static array of the first 100 primes, which is overkill already. That’s clearer and shorter but your dynamic generation is actually more powerful, so you should probably use it since you already wrote it.

Thanks, Jules, and thumbs up on making an awesome first impression not just of your code, but your personal support.

#4

Thanks very much!

The code I posted above was actually full of bugs, but I’ve checked in a new version that seems to work now.

#5