From: Mark Wooding Date: Sat, 21 Sep 2019 10:37:24 +0000 (+0100) Subject: pock.1: Mention Baillie-PSW and why `pock' is still useful. X-Git-Tag: 1.3.0~8 X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/catacomb-python/commitdiff_plain/13c5ef3999d1779ddd625fc831ff757407efb840?hp=ba2dd9e204a85b753b71df4c67aa5684e15f54b7 pock.1: Mention Baillie-PSW and why `pock' is still useful. --- diff --git a/pock.1 b/pock.1 index 22dab5c..8f0fc23 100644 --- a/pock.1 +++ b/pock.1 @@ -157,14 +157,34 @@ and often they must pessimistically assume that the number was chosen maliciously, and the worst-case .IR n /4 -bound is the best one can do. +bound is the best one can do using the Rabin\(enMiller test. For large candidates, this is inconveniently slow. (Also, many implementations incorrectly use a number of iterations suitable for randomly chosen primes for testing candidates of unknown provenance.) .PP -The +There +.I are +stronger probabilistic tests. +A combination of Rabin\(enMiller and +Grantham's Frobenius test +is known as the +Baillie\(enPSW test +(after Baillie, Pomerance, Selfridge, and Wagstaff); +there are +.I no +known composites which pass this test, +nor is it known how to construct any. +On the other hand, it's been conjectured that +infinitely many Baillie\(enPSW pseudoprimes exist. +While it may be reasonable to assume +the strength of the Baillie\(enPSW test, +it must be borne in mind that this +.I does +constitute a security assumption. +.PP +By contrast,the .B pock program will generate prime numbers of sizes suitable for use in cryptography,