P.I.E.S. - Prime Internet Eisenstein Search

[axn]

Hmmm... Perhaps https://en.wikipedia.org/wiki/Eisenstein_reciprocity can be used to intelligently select the base?!

[Batalov]

Maybe it can.
LLR treats this as any a^b-a^c+1 form, so it just goes brute force.

[axn]

I don't understand the math properly, but one quick observation was that, in this case, 11 was the first prime that didn't divide N-1 (next one is 19). Is this a necessary condition? If so, this is something that can be cheaply implemented.

[R. Gerbicz]

Originally Posted by Batalov

I ended up running two 18-threaded N-1 tests: one that started from a=3, then continued with a=5... and the other started from scratch with a=11 (in another folder and with affinities set to the 18 ht cores of the second 9-core chip). Both ran with 7.6 ms / iter speed.

The a=11 won the jackpot in one go, the a=5 run again didn't get the proof (one of the three a^((N-1)/f)-1 was not coprime to N) and continued into a=7 and I killed it and released the instance.

It would be enough to find "a" for that gcd(N,(a^((N-1)/5119)-1)=1 and a^(N-1)=1 mod N,
plus an ultra cheap square test due to Brillhart-Lehmer-Selfridge cuberoot theorem.
It is well known:
if F^2<n=c2*F^2+c1*F+1<F^3, where 0<=c1,c2<F and there exists an integer d for
that d^(n-1)=1 mod n and for every p|F it is true that gcd(d^((n-1)/p)-1,n)=1.
Then n is prime if and only if c1^2-4*c2 is not a square number.

To increase our chances to find a good d base: select the largest p prime factors of N-1 until you don't reach
that if the product of these is F then F^3>n. (do this in an intelligent fast way, because here N-1 has got large prime powers). Optionally include the smallest p=2 divisor of N-1,
since d^((n-1)/2)=(d/n) Legendre symbol (here assume that n is prime), what you can get very quickly, and
obviously if (d/n)=-1 then d^((n-1)/2)=-1 mod n so gcd(d^((n-1)/2)-1,n)=1, and throw away d if (d/n)=1.

Here note that in the theorem if it would be turn out n<F^2, then it is the strong Lehmer test (and you don't need the square test).

[Batalov]

These are great ideas.

For me, the two-fold goal was to a) make the N-1 test reasonably fast (faster than 3 weeks) and b) not take up on a burden of proof that the changes to LLR are not leading to false positives.
Otherwise, to an uninitiated it could look like "he is changing the program(s) to convince us that his candidate is prime".

This was achieved by adding just one line (flipping the nitrous switch of the gwnum lib) to LLR's code for this one particular test. So if it wouldn't have worked, then it would have been either George's or Jean's fault (ha-ha but seriously ).

It is of course an exciting but voluminous work to substantially change LLR code, then thoroughly test it... and then use it. Or to parallelize PFGW (because it has BLS vs a vanilla Pocklington's) which is quite likely possible.
That's a separate story and it will be done in preparation for the upcoming hits in the b^{2[SUP][SIZE=1]20[/SIZE]}[/SUP]-b^{2[SUP][SIZE=1]19[/SIZE]}[/SUP]+1 series that will be hopefully coming before spring. The initial PRP hits will be streamed off CycloCPU or the now well-trusted PhiExtensions of P95, so we already have all the tools for the bulk of the search.

[paulunderwood]

Originally Posted by Batalov

That's a separate story and it will be done in preparation for the upcoming hits in the b^{2[SUP][SIZE=1]20[/SIZE]}[/SUP]-b^{2[SUP][SIZE=1]19[/SIZE]}[/SUP]+1 series that will be hopefully coming before spring.

These/it could be over 5 million digits!

[Batalov]

Well, they could up to be 6.1M+ digits in size, but they will not reach the M20996011 spot.

To equal it, need b>1,065,690 but rounding errors are out of bounds for even lesser b values.

[paulunderwood]

Originally Posted by Batalov

Well, they could up to be 6.1M+ digits in size, but they will not reach the M20996011 spot.

To equal it, need b>1,065,690 but rounding errors are out of bounds for even lesser b values.

Of a million initial values, what percentage is sieved out? Do I recall correctly you saying that you can sieve to 61 bits?

[Batalov]

We can sieve well beyond 61 bits, but currently most sieves we did were stopped at about 61-63 bits. We will go higher with Phi(3,-b^2[SUP]19[/SUP]).

There is ~40% candidates left for this series. For smaller m degrees, there were less candidates, e.g. ~30% for m=49152, ~38% for m=393216. This has primarily to do with the least allowed divisor: when 6m+1 is prime, then you get immediately sparser candidate pool.

m	p_least
16384	786433
24576	147457
32768	786433
49152	1179649
65536	786433
98304	1179649
131072	786433
196608	1179649
262144	14155777
393216	14155777
524288	28311553
786432	14155777
1048576	69206017
1572864	28311553

[paulunderwood]

Compare Serge's multi-core run:

Using generic reduction FMA3 FFT length 1440K, Pass1=320, Pass2=4608, 18 threads, a = 11
11^((N-1)/5119)-1 is coprime to N!
11^((N-1)/7)-1 is coprime to N!
11^((N-1)/2)-1 is coprime to N!
143332^786432-143332^393216+1 is prime! (4055114 decimal digits)  Time : 105281.520 sec.

to UTM's single core:

Phi(3,-143332^393216) is prime! (606135.7958s+1.1064s)
[Elapsed time: 7.02 days]

[Batalov]

It looks about right. The scaling was flat as soon as you leave the boundaries of a physical chip. I could have just as well run only 9 threads (it was a 9-core Xeon), with the effective scaling ~6x.

On a side, I have run a dozen simple-form smaller known primes for testing "no false negatives"/"no lost functionality"; all passed.