Re: [PrimeNumbers] Re: Infallible isprime(p) routine for 0<2^32
- On 3/11/2013 8:54 PM, WarrenS wrote:
>Actually, Jeff Gilchrist and I performed the double check on the data. I wrote
>> I have a hunch that BPSW may have been tested up to 2^64, if Jan Feitsma,
>> and followers, have done their stuff aright?
> --My claims about infallibility up to 2^64 rely on a database compiled by Jan
> Feitsma of all strong psp(2) up to 2^64. Actually all fermat(2) pseudoprimes
> up to 2^64.
> The question is, is Feitsma correct? Yes in the sense his dataset agrees with
> previous smaller (but still huge) computations by others. Maybe No, in the
> sense he might have had a bug that only kicks in above, say, 0.8 * 2^64.
> Until somebody redoes his computation independently there will remain room
> for doubt. Nobody wants to since it could take a CPU-year or more, plus a
> considerable amount of intelligence to rediscover his or comparable ideas.
the majority of the double-checking code, which was independent of Jan's code
since it was only based on my understanding of his algorithms. The majority of
the double-check computations were performed by Jeff Gilchrist and the
"big-iron" he had access to. So, the database based on his algorithm has been
double checked. You can see Jan's latest post about this on the mersenneforum here:
The hope is that somebody, perhaps someone on this list, will go through his
algorithm and verify that _that_ is correct. You can find all the details in
the links Jan provided in the above post.
- On 3/13/2013 5:47 AM, Phil Carmody wrote:
> No I couldn't. That's so overly verbose and redundant it makes me twitch, I canApologies, my Pari/GP script-fu is definitely not on par with DJB's. I just
> barely bring myself to repeat it!
> "lift(Mod(p*s, lift(znorder(Mod(2,s))))) == 1" is just
> "p*s % znorder(Mod(2,s)) == 1"
> Having 3 exit conditions to the loop is overkill too.
wanted to provide a script so that people could plug and chug an r,p pair to see
what psp's would be generated. Also, I didn't know that the % (mod) operator
still worked in Pari. I thought everything had to be done with Mod(). Thanks
for that insight.
> The latter worries me a bit, as it might imply wasted effort. I'm trying toAnd apologies here too, I mis-remembered a statement from his Category S page
> picture how these duplicates arise. Given a n, the maximal prime factor p|s is
> uniquely defined, and r as order_2(p) is uniquely defined. Therefore n can only
> appear with pair (r,p)?
and mis-spoke by applying it to the Category E psp's.
On 3/14/2013 11:02 AM, WarrenS wrote:
> 2. Consulting the Cunningham project pages,
> every Mersenne-form number 2^r - 1 now is fully factored if
> r<929. Apparently the first two open cases are r=929 and 947
> yielding 214 and 217 digit numbers to factor.
An update here: M929 has been factored, and a group of people have already
started factoring M947. You can find the factor for M929 here:
And, you can see who is factoring which Cunningham number here:
And more importantly, you can find all known*1 factors for all important*2
numbers in the online factor database here:
Once there, you can type in 2^929-1, and it will show you all the factors of
that number and that it is Fully Factored (FF). Currently, you can type in
2^947-1 and see that it is a CF, composite number, with factors known, but not
yet fully factored.
*1 = All known factors that have been stored into the factordb.
*2 = All numbers that people are interested in and store in the factordb.
Also, the factordb stores prime numbers too. Below 300 digits it will just
prove the number prime, and above that it will accept Primo certificates and
verify them locally.