Bug in Flint primality testing

[Bill Hart]

Hi all,

Unfortunately we (or rather Fredrik) has discovered a bug in fmpz_is_strong_probabprime which in turn (theoretically at least) affected fmpz_is_probabprime and most likely also fmpz_is_prime (though the impact there might not have been great).

The bug has now been fixed in trunk and test code has been added.

This particular bug should not have gone unnoticed for so long and is rather an embarrassment. It's probably one of the five most serious bugs ever found in Flint.

Primality tests tend to be very hard to fool, so detecting bugs through standard testing is rather hard.

This is not the only bug that has ever been found in Flint primality testing, so we urge everyone using it to treat it with suspicion, i.e. assume that it is not rigorous for your needs until you have done your own tests to verify that it is.

Fortunately there has been no release with a competitive fmpz_is_prime function that has been carefully examined by us, so we most probably caught this just in time. However, we are aware that a number of people have been using that functionality already, which is why I'm reporting it here.

Bill.

[Bill Hart]

Sure, the algorithm in the affected function was dead simple. It's just a simple modular exponentiation. There was just a dumb bug in the code. All the algorithms we use have proofs.

The main primality proving algorithm used is APRCL, and I refer to the book Primes: A Computational Perspective by Crandall and Pomerance for details of all the (many) algorithms we use for primality testing.

Unfortunately, APRCL is only as good as the implementation of the functions that make it up. In this case, one very low level function had a bug.

But you are talking about tens of thousands of lines of code. Primality testing and factorisation are some people's life's work. Our implementation is not even that complicated. It only needs to be good enough for a general purpose library. There are far better libraries out there which are faster, but exceedingly more complex.

Bill.

On Wed, 1 Apr 2020 at 05:55, Thomas DuBuisson <thomas.d...@gmail.com> wrote:

Is there no possibility for a specification of the algorithm and a proof?

--

---
You received this message because you are subscribed to the Google Groups "flint-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to flint-devel...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/flint-devel/CAB0xFnvtJfRnuv4Qi6OKJ1a%2B_swneRWKc7s9%2BHKcJPv90ROszg%40mail.gmail.com.

--

---
You received this message because you are subscribed to the Google Groups "flint-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to flint-devel...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/flint-devel/CAOk36JhsvCq-CAoBNjNCLPU0nL6ihVa_SO3FwV1fFPGMQBmAwA%40mail.gmail.com.