From: Mark Wooding <mdw@distorted.org.uk>
Date: Sat, 17 Nov 2018 19:21:43 +0000 (+0000)
Subject: math/: Implement Grantham's Frobenius (primality) test.
X-Git-Tag: 2.5.0~20
X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/catacomb/commitdiff_plain/6001a9ffafa1e77b2d192938d79e6da80febdc43?hp=6001a9ffafa1e77b2d192938d79e6da80febdc43

math/: Implement Grantham's Frobenius (primality) test.

This is a rather heavyweight test which is effective when checking
possibly adversarial numbers.

There are no known composites which pass both this test and the
Miller--Rabin test with witness 2 (although infinitely many are
conjectured to exist); the combination is called the `Baillie--PSW'
test (after Baillie, Pomerance, Selfridge, and Wagstaff).  Modify
`pgen_primep' to use Baillie--PSW.

Since Baillie--PSW is somewhat faster than the many rounds of Miller--
Rabin which `pgen_primep' used to use, celebrate by raising the `keen'
threshold in the `dh-param.c' test.

This work was prompted by the paper `Prime and Prejudice', by Martin
R. Albrecht, Jake Massimo, Kenneth G. Paterson, and Juraj Somorovsky;
though, since Catacomb already used 32 iterations of Miller--Rabin with
random witnesses, I can confidently state that the previous
implementation was inefficient but secure when used with a good
randomness source.
---