On 15/08/2013 07:49, Case Van Horsen wrote: > Hi, > > A user of gmpy2 reported that gmpy2.next_prime() returned composite > values quite frequently. For example: > >>>> gmpy2.next_prime(2357*7069-1)==2357*7069 > True > > I believe this is caused by the following line in next_likely_prime.c: > > if (mpz_miller_rabin (p, 2, rnd)) > > The Miller-Rabin test is only repeated twice. IIRC, 25 repeats used to > be the default.
Hi Case, My apologies for this late response. The aim of this test is not to produce probable primes with a low probability that they are composite but rather to rapidly find candidates that can then be tested for primality using a method chosen by the user. So we expect this routine to be followed by a much high quality primality test, which means that adding more Miller-Rabin rounds would defeat the whole purpose. The low quality Miller-Rabin test is only there after trial division to avoid returning too many false primes when it would be better to continue the fast forward search (returning too many would probably mean the routine would be reentered and this would carry the cost of re-initialising the internal tables). So the focus of this test is on speed, not accuracy. Brian -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to mpir-devel+unsubscr...@googlegroups.com. To post to this group, send email to mpir-devel@googlegroups.com. Visit this group at http://groups.google.com/group/mpir-devel. For more options, visit https://groups.google.com/groups/opt_out.
