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

Expand Messages
• ... --don t understand question. ... --not so. I think you are right eventually (i.e. after you ve done 9999 spsp tests to different random bases, the 10000th
Message 1 of 37 , Mar 11, 2013
--- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...> wrote:
>
> --- On Mon, 3/11/13, WarrenS <warren.wds@...> wrote:
> > If it is your goal to choose X so
> > there are few spsp{2, X},
> > then X=735 does pretty well.
> > There are 57 spsp{2, 735} below 2^32
> > and   1149508 spsp{2, 735} below 2^64.
>
> How many yield square roots of -1 that aren't the same (or additive inverses) from the two SPRP tests?

--don't understand question.

> > The latter is substantially better than Broadhurst's
> > X=858945; there are 1311216 spsp{2,858945} below 2^64.
> > I make no claim 735 is best, it is merely comparatively
> > good.
> >
> > It would probably be possible to devise an infallible
> > isprime test for
> > <=64-bit integers by performing spsp(2) and spsp(735)
> > tests, and then hashing
> > the 1149508 failures into 8192 bins (each bin representing
> > about 140; need to
> > devise the hash function to get good equidistribution)
> > and then the content of that table entry tells you which
> > base B to use for a final spsp(B)
> > test.  (B chosen to kill all fakes in its hash-table
> > bin.)
>
> Once you've got a SPRP, on average each new SPRP test removes only a quarter of the fakes. Culling 140/140 with one test seems unlikely. I'm not sure if that quarter includes the square (and higher) root hack.

--not so. I think you are right eventually (i.e. after you've done 9999 spsp tests to
different random bases, the 10000th one will only cut your set of fakes by about a factor of 4) but my computer tells me that if you've only done one or two spsp tests, then
the next one will kill a lot more than a factor of 4. Specifically,

1. There are 31894014 spsp{2} below 2^64.
2. There are 1149508 spsp{2,735} below 2^64.
Note, that was not a cut by a factor 4, it was a cut by a factor of 27.7.
3. There are 96827 spsp{2,325,9375} below 2^64.
Again, that was not a cut by factor of 4, it cut by factor at least 11.9.

I can explain the reason why this is, but you probably can see it already.
So in my proposed plan, we need to cull 140/140 with 1 test. Assume 1 test
(given that 2 spsp test already performed) typically cuts by factor 11.9 hence
would cut 140 down to about 12 fakes. However, assuming Poisson statistics we expect
among exp(12)=162755 bases B, there will exist one which will kill all 140.
So simply search and find that B. This ought to be a feasible computation.

> > This primality test, in net, would involve three spsp tests
> > and one hash-table lookup in a table with 8192 entries; you
> > could probably compute the table in a few days.
>
> The \$620 test (not \$640) can already be performed with a cost of 3 SPRP tests, so this wouldn't be an improvement over what's already done.

--well, it probably would be somewhat improved, since the "cost of 3" claim I doubt
was really true. But it would be annoying since you'd need an 8192-entry table.

> > I am in fact working on an infallible 64-bit isprime test,
> > but not using the method I just outlined,instead based on
> > combining an spsp(2) test with a Lehmer test.
> > I'll report on that later, if I succeed.
>
> In the kind of science I like, reports of failure are useful too. Knowing what alleyways are blind is useful, but also someone else might have a final insight to patch things up.

--well, stay tuned. My plan here is like the \$620 (I heard \$640, but ok) test, but I hope somewhat simpler + superior.
• ... 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, 2013
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.