On Wed, May 27, 2015 at 02:06:12PM +0200, Aris Adamantiadis wrote: > If the primality test is such a problem, one could implement a variant > to the AKS polynomial time primality test: > https://en.wikipedia.org/wiki/AKS_primality_test > https://math.dartmouth.edu/~carlp/aks041411.pdf > > This test (and variants) are not statistical. I have no idea if they > work in reasonable time on 1024-4096bits prime candidates. > > Aris > > Le 27/05/15 04:55, mancha a écrit : > > 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 Though PRIMES IN P has been heavily optimized since it's first version, it's still O(log^7 n) or so. Compare that to Fast-ECPP which is around O(log^4 n). Also, for our purposes we're going up to 8192 bit numbers not just 4096. Unfortunately, neither PRIMES IN P nor tests such as the near poly-time APR generate proofs. So, there's no quick way to verify someone else's result. --mancha
Attachment:
pgpNDFumQU3mG.pgp
Description: PGP signature
_______________________________________________ openssh-unix-dev mailing list openssh-unix-dev@xxxxxxxxxxx https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
