Implement the Baillie-PSW primality test

It has long been known that pure Miller-Rabin primality tests are
insufficient. "Prime and Prejudice: Primality Testing Under Adversarial
Conditions" https://eprint.iacr.org/2018/749 points out severe flaws
in many widely used libraries. In particular, they exhibited a method to
generate 2048-bit composites that bypass the default OpenSSL (and hence
LibreSSL) primality test with a probability of 1/16 (!).

As a remedy, the authors recommend switching to using BPSW wherever
possible. This possibility has always been there, but someone had to
sit down and actually implement a properly licensed piece of code.

Fortunately, espie suggested to Martin Grenouilloux to do precisely this
after asking us whether we would be interested. Of course we were!
After a good first implementation from Martin and a lot of back and
forth, we came up with the present version.

This implementation is ~50% slower than the current default Miller-Rabin
test, but that is a small price to pay given the improvements.

Thanks to Martin Grenouilloux <martin.grenouilloux () lse ! epita ! fr>
for this awesome work, to espie without whom it wouldn't have happened,
and to djm for pointing us at this problem a long time back.

ok jsing

0 files changed, 0 insertions, 0 deletions