On Tue, May 26, 2015 at 03:10:01PM -0400, Daniel Kahn Gillmor wrote: > Does anyone have a pointer to any decent free software for generating > and verifying primality proofs? > > --dkg OpenSSH generates strong pseudoprimes to k random bases (that if prime would be "safe primes"). I think Darren uses k=100 (confirmation?) so the way the math works out, each number he generates has at most a 1/(4^100) probability of being composite. In comparison, it's estimated the odds of getting crushed to death by a vending machine are 1 in 112 million. Death-by-chocolate-bar is about 14,347,661,109,455,270,317,338,947,253,046,094,665,376,812,444,489,221 more likely to happen to you than having a given "Darren-prime" turn out to be composite. The take-away, of course, is to always snack responsibly. Nonetheless, the most we can currently say is the numbers are almost surely prime. Certainty would be nice. ECPP is the fastest prime proving algorithm that also provides certificates (I think) and PRIMO is the king-of-the-hill implementation (others exist but are significantly slower with bigger numbers). Though as you mentioned PRIMO's not libre (just free), the math in the certificates is open-source and that's really the critical part here. The proofs themselves are sequences of steps that at each step (except the last) prove a number N is prime if a smaller number R is prime. Every subsequent step takes its N from the previous step's R and this continues until we arrive at an R < 34*10^13 because such an R can be proven prime if it is a strong pseudoprime to the base of the 7 primes smaller than 19 (i.e. 2, 3, 5, 7, 11, 13, 17) TL;DR With PRIMO's help, I've proved the first 200 strong pseudoprimes in the latest v1.12 moduli file are indeed prime. Darren, so far you're batting a thousand! I've uploaded my proofs to factordb.com for independent verification and complementary confirmation proofs. For example, check out the 4th prime in Darren's new moduli file: https://tinyurl.com/pg66aq5 As I write this I've checked through #209. Those with spare CPU cycles on 64-bit Linux can help with the 65 strong pseudoprimes remaining (#210 to #274). Those who wish to help should get PRIMO [1] and grab the full set of input files I made: http://sf.net/projects/mancha/files/misc/openssh-moduli-20150522_primo.tar.bz2 The 7680-bit moduli (#225 - #248) and 8192-bit moduli (#249 - #274) are up for grabs. Probably best if you claim your range to avoid effort duplication. --mancha PS In addition to factordb.com, ecpp-dj [2] can verify PRIMO certs. ecpp-dj also proves primality but it is slower than PRIMO and more importantly its cert format can't be independently verified. ------ [1] http://www.ellipsa.eu/public/primo/files/primo-411-lx64.7z [2] http://sti15.com/nt/ecpp-dj-1.04.tar.gz
Attachment:
pgprgfdu1fXGz.pgp
Description: PGP signature
_______________________________________________ openssh-unix-dev mailing list openssh-unix-dev@xxxxxxxxxxx https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
