Whoah, it just does trial division up to 1000 then uses a *single* *random* base for a strong pseudoprime test!
I have a definite problem with this. What is the probability of returning a composite? Assuming the factors are bigger than 1000, it is like 1/4. This is going to break a *lot* of code! Bill. 2009/12/4 Bill Hart <[email protected]>: > I've looked into this slightly more and the values I was printing out > were not the values it claimed were prime, but the values sent to > mpz_nextprime. > > The values it is now claiming prime are: > > 3270403 = 1279*2557 > 3387781 = 1063*3187 > 21785201 = 1019*21379 > > So these all have "large" factors. So what is the algorithm we use? > Surely any sensible "likely prime" algorithm should pick up factors > like this? I remain concerned that we have replaced an algorithm which > for all intents and purposes returned a prime, with one which very > often returns composites. That is going to break an awful lot of code > out there. > > If the algorithm uses random values in any way then it will be > difficult to replicate this issue. > > Bill. > > 2009/12/4 Case Vanhorsen <[email protected]>: >> On Tue, Dec 1, 2009 at 9:33 AM, Bill Hart <[email protected]> >> wrote: >>> It is the code Jason wrote: >>> >>> mpz_nextprime -> mpz_next_likely_prime ->mpz_likely_prime (by JM). >>> >>> At one point I switched over to the other implementation, but Jason >>> raised the trial factoring bound and the problems seemed to go away. >>> So it is currently using his code. But on win32 it is problematic for >>> me. For example it declares the following likely prime: >>> >>> 3270390, 3387761, 21785199, 3270396 >>> >>> All of these have very small factors. >> >> I tried to duplicate the failures on my computer but I couldn't. I >> tried both a Win32 VS build and a MinGW build via GMPY. I just called >> next_prime with all the numbers from 3270390 back to the previous two >> primes and I was getting correct results. How were you generating >> these failures? >> >> casevh >>> >>> Bill. >>> >>> 2009/12/1 Jeff Gilchrist <[email protected]>: >>>> On Tue, Dec 1, 2009 at 12:07 PM, Bill Hart <[email protected]> >>>> wrote: >>>>> mpz_nextprime seems to report lots of composites as primes on 32 bit >>>>> machines, including some even numbers! Is this the same issue as we >>>>> had on 64 bit machines? >>>> >>>> Is that the old built-in function or the new one Jason developed? >>>> >>>> Jeff. >>>> >>>> -- >>>> >>>> You received this message because you are subscribed to the Google Groups >>>> "mpir-devel" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/mpir-devel?hl=en. >>>> >>>> >>>> >>> >>> -- >>> >>> You received this message because you are subscribed to the Google Groups >>> "mpir-devel" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/mpir-devel?hl=en. >>> >>> >>> >> >> -- >> >> You received this message because you are subscribed to the Google Groups >> "mpir-devel" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/mpir-devel?hl=en. >> >> >> > -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
