[Mono-devel-list] Two BigInteger.isProbablePrime bugs...

[Pieter Philippaerts]

Hey there,
I've been using the BigInteger class for a while now, and I've come across
two bugs in the isProbablePrime method.

The first bug has to do with small primes. If you initialize a BigInteger
instance with a small prime, isProbablePrime will always return false. If
you look at the for loop in the isProbablePrime method, it's easy to see why
it does this. This bug can be fixed by changing the for loop to this:
    for (int p = 0; p < smallPrimes.Length; p++) {
        if (this == smallPrimes [p])
            return true;
        if (this % smallPrimes [p] == 0)
            return false;
    }

The second bug has to do with the primality test of large primes. If I
initialize the BigInteger class with one of the primes from the "OAKLEY Key
Determination Protocol" [RFC 2412, http://www.faqs.org/rfcs/rfc2412.html],
the isProbablePrime method always returns false even though the numbers are
definitely prime [this should never happen -- a primality test should never
mark a prime as a composite number]. I've attached a test application so you
can reproduce the behavior [the code uses the BigInteger.Parse method I
posted here a few days ago -- I've included a commented version of this
method in the file if you don't have this method].

Regards,
Pieter Philippaerts
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: BigIntBug.cs
Url: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20031120/772d0235/attachment.pl