search for: is_prime

On Fri 2015-05-22 00:06:29 -0400, Darren Tucker wrote: > On Thu, May 21, 2015 at 11:26 PM, Matthew Vernon <matthew at debian.org> wrote: >> >> You will be aware of https://weakdh.org/ by now, I presume; the >> take-home seems to be that 1024-bit DH primes might well be too weak. >> I'm wondering what (if anything!) you propose to do about this issue, >>

...ty ("Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness"). Taking the final integer in that sequence (a(11)) fails even the default 25-round M-R test in gmp: >>> k = gmpy2.mpz(3825123056546413051) >>> gmpy2.is_prime(k) False >>> Indeed, the arxiv suggests that in 2012 people were still writing proofs about a(11) for this sequence: http://arxiv.org/abs/1207.0063 but i see no evidence that an algorithm for generating a(n) where n is arbitrarily large exists. Does such a thing exist? > yes, us...

On Tue 2015-05-26 12:57:05 -0400, Hubert Kario wrote: > creating composites that will pass even 100000 rounds of Miller-Rabin is > relatively simple.... > (assuming the values for M-R tests are picked randomly) Can you point me to the algorithms for doing that? This would suggest that we really do want primality proofs (and a good way to verify them). Do those algorithms hold for

...rimality test on bases <= n-th prime does not reveal compositeness"). >> >> Taking the final integer in that sequence (a(11)) fails even the default >> >> 25-round M-R test in gmp: >> >>> k = gmpy2.mpz(3825123056546413051) >> >>> gmpy2.is_prime(k) >> >> False > > I'm quite sure that this means that gmpy doesn't use pure M-R with randomly > selected witnesses. https://gmplib.org/manual/Prime-Testing-Algorithm.html#Prime-Testing-Algorithm suggests is chooses a random base, but it also runs some non-M-R tests...