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

axn · 2017-01-31, 03:12

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

Batalov · 2017-01-31, 05:05

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

axn · 2017-01-31, 08:06

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 · 2017-01-31, 09:34

Quote:

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 · 2017-02-01, 07:21

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 · 2017-02-02, 06:12

Quote:

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 · 2017-02-02, 19:08

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 · 2017-02-02, 19:35

Quote:

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 · 2017-02-05, 20:14

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.

Code:

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 · 2017-02-06, 13:20

Compare Serge's multi-core run:

Code:

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:

Code:

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

Batalov · 2017-02-06, 15:49

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.

2017-02-05, 20:14	#97
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2516₁₆ Posts	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. Code: 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Prime 95 and internet connection issue	Jwb52z	Software	10	2013-01-30 01:09
Twin prime search?	MooooMoo	Twin Prime Search	115	2010-08-29 17:38
Prime Search at School	Unregistered	Information & Answers	5	2009-10-15 22:44
Prime Search on PS-3?	Kosmaj	Riesel Prime Search	6	2006-11-21 15:19
Running prime on PC without internet-connection	Ferdy	Software	3	2006-04-25 08:53

2017-01-31, 03:12	#89
axn Jun 2003 13DA₁₆ Posts	Hmmm... Perhaps https://en.wikipedia.org/wiki/Eisenstein_reciprocity can be used to intelligently select the base?!

2017-01-31, 05:05	#90
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·47·101 Posts	Maybe it can. LLR treats this as any a^b-a^c+1 form, so it just goes brute force.

2017-01-31, 08:06	#91
axn Jun 2003 2×3×7×11² Posts	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.

2017-02-01, 07:21	#93
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·47·101 Posts	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.

2017-02-02, 19:08	#95
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×47×101 Posts	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.

2017-02-06, 15:49	#99
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·47·101 Posts	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.