Browse Groups

• ## Re: Infallible isprime(p) routine for 0<2^32

(37)
• NextPrevious
• ... --oh, that s interesting. Worley s code should definitely be faster than mine, unless its spsp implementation sucks (actually, it does suck in the sense
Message 1 of 37 , Mar 11
View Source
--- In primenumbers@yahoogroups.com, David Cleaver <wraithx@...> wrote:
>
> You can see a good post about using a single spsp test to prove any number <
> 2^32 prime/composite over on the mersenneforum:
> In that post, he has a hash table of size 1024 that works on all numbers < 2^32.
>
> Warren, I'm curious, would you time this code against yours to see which one
> comes out faster?
>
> Someone else was able to get n < 2^64 down to 4 spsp tests, (3 fixed, and one
> into a hash). I didn't see anyone reduce it to 3 spsp tests for n < 2^64.
> Hopefully something like that will show up some day soon.
>
> -David C.

--oh, that's interesting. Worley's code should definitely be faster than mine,
unless its spsp implementation sucks (actually, it does suck in the sense he fails to use the radix-8 trick I use) in which case hybridizing our codes would be faster than either.

--My plan for 2^64 infallible test with 3 spsp tests is going to work, but it will take
50 hours more computing for me to find the hash table (estimated based on the computing it has done so far).
• ... Apologies, my Pari/GP script-fu is definitely not on par with DJB s. I just wanted to provide a script so that people could plug and chug an r,p pair to
Message 37 of 37 , Mar 14
View Source
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 can
> 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.

Apologies, my Pari/GP script-fu is definitely not on par with DJB's. I just
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 to
> 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 apologies here too, I mis-remembered a statement from his Category S page
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,
> http://homes.cerias.purdue.edu/~ssw/cun/index.html
> 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:
http://homes.cerias.purdue.edu/~ssw/cun/page125
And, you can see who is factoring which Cunningham number here:
http://homes.cerias.purdue.edu/~ssw/cun/who
And more importantly, you can find all known*1 factors for all important*2
numbers in the online factor database here:
factordb.com
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.

-David C.
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.