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

[Batalov]

Approximately a thousand dollars worth of EC2 g2.2xlarge (with GRID K520s) time yielded the next term for the OEIS sequence A246119 (n=17; b somewhat higher than expected; details will follow soon, after the doublecheck/N-1 proof with PFGW). Using three idle Ivy Bridge cores, I also ran quite a bit of my k=5 Proth reservation with waterline now advanced to around n~=10,000,000...

Now, a bit of final overhead is needed for the stragglers to prove the minimality of b. Thanks to Yves and Anand for some excellent coding. Without Cyclo, at b > ~65000, cycLLR (and gwnum that is powering it) switches from special to general FFT which is many times slower; I already had some work done for both n=16 (up to b<=75000) and n=17 (up to b<=60000), but both need quite a bit of more heavy lifting and for both Cyclo was the only way to go effectively. CycloSv by axn also helped to eliminate additional work by effective sieving.

I asked and received an increase for up to 20 spot instances in two zones. EC2 folks were quite helpful (late in January, I launched five nodes without checking "spot", accidentally, and before I realized this by watching cost report I was already out of a hundred bucks instead of normal ten bucks; they generously refunded me... a minor anecdote of course, but a pleasant one, nevertheless).

[axn]

Congratulations!

FYI, there has been reported cases of the sieve reporting bad factors, due to occasional composite inputs that beats the PRP test for candidate factors. As a result, you must check that all factors actually divide the number. Hopefully, you've been doing that, but if not, you'll have to check the factors for false positives

[Batalov]

Yes, I have that perl reformatter into the Mod(b,f)^n ... form, which I then pipe to gp.
I'll do the final tally when I will be done with the batch as it is.

The PFGW test will take 15 hours (3 of which have passed), even on an AVX capable comp. The Cyclo test takes 2300s on the K520, and for comparison, 1660s on my 570, so those K520 are pretty worth the 6.4 cents per hour (approximately 4c per candidate times ~25,000). I will report the prime tomorrow early afternoon. I will report the OEIS extension only later when I will run all needed tests.

[axn]

New version 0.5:

Fixed ETA calculation. Was off by a factor of 50% (if it said 1hr, it would actually take 1.5hr).
Changed ETA update frequency from once every 3 seconds to 10 seconds


Attached are the source, win32 exe (CUDA 3.2), and compile scripts for windows and linux.

[Batalov]

192098^262144 - 192098^131072 + 1 is prime. (Cyclo on a K520 2311.0 sec., err=2.88e-02, 1385044 digits)

Double check on GTX 570 (with Cyclo 1.0.1):
192098^262144 - 192098^131072 + 1 is a probable prime. (1655.9 sec., err=2.88e-002, 1385044 digits)

N-1 proof:
Primality testing Phi(3,-192098^131072) [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 7
Generic modular reduction using generic reduction AVX FFT length 480K, Pass1=384, Pass2=1280 on A 4601016-bit number
Calling Brillhart-Lehmer-Selfridge with factored part 47.15%
Phi(3,-192098^131072) is prime! (54402.0486s+0.3578s)

[Batalov]

Here is a bit funny prime: Phi(5, pq-1), where p=187·2^110513-1, q=409·2^129185-1 are primes.

One can observe that Phi₅(x)-1 has factors x and x+1, and in this case x is 46% factored, and x+1 is fully factored; so that altogether allows for the 36.5% factored N-1 proof. Similarly, Phi₁₀(x)-1 has factors x and x-1 and one can be fully factored and the other >33.3% factored.

Similar numbers have form Phi₅(x) or Phi₁₀(x), where x = { pq | pq-1 | pq+1 } (one form for each Phi₅ and Phi₁₀ is usable every time). One can combine all known small Proth and Riesel primes such that 33% is reached (in a nutshell, one needs p <= q < p² to achieve the >33.3% proof.)

P.S. Another one is Phi₇(p) (i.e. p⁶+p⁵+p⁴+p³+p²+p+1), where p=5978493*2^150006-1. With 270979 decimal digits, it is a bit short of entering the UTM prime database.

[Batalov]

I've systematically scanned the Phi(3,-b^2^15) P.I.E.S. series and here is the chart for the numerologists to ponder.

This is the distribution of the 30 b values for which Phi(3,-b^2^15) is prime, and it is fairly clumpy in parts: there are seven primes for b<46,000; there are none for some stretches of >130,000 in length; there are a couple very close pairs: e.g. (570986, 571472) and (589179, 589797). I know for a fact that there are people in the audience who would cancel their reservation for their chunk "next" to a recent prime (because "there can't be a prime there now; my prime was stolen, now this range is crap!"); there are some who would look only for prime b values, etc. The truth is that after the sieving is done, all the survivor candidates (in their size bins) have equal chances to be prime as a plain function of their size. It is exactly the same for any class of primes: Mersenne series, any Proth/Riesel series*, Gaussian-Mersenne, partition numbers, you name it. Marvel the Poisson process at its best:

____________
*...and with k being a Proth or a Riesel number, it is also true. That probability is simply zero and equal for all candidates; however, there will be no candidates left in the sieve after the covering set has done its job.

[axn]

Random observation: It should be relatively easy to adapt Cyclo to do a primality proof instead of PRP test in the same amount of time, by implementing Pocklington's Theorem. http://primes.utm.edu/prove/prove3_1.html

Just noting, what with all the Cyclo primes currently being found

[Batalov]

Sure! So far, Yves just recently wrangled that prime-specific pattern that happens during last iterations of squaring for some odd b values. So, one wouldn't want to jump to another algorithm before debugging that; but now would be a great time. He added the 80-bit math, he wrote, and it is used in last iterations.

In fact, today I found a very peculiar rounding error reported: 9.99e-01 , so the weird rounding errors are still possible albeit very rarely, even with v.1.1.0. (All previous PRPs returned either average rounding error or the flat value of 5.00e-01 and 'composite' verdict.)

My hunch is that the rounding error of ~ 1 could happen if trunc works in the mode 'round toward zero' and the true value (with carries) happened to go into negatives. Otherwise, of course, Occam's razor would tell us that rounding error > 0.5 is not possible.
But I haven't looked in the source.

[axn]

While I was thinking about how to efficiently implement the primality test, a thought occurred to me. Currently there is no "independent" double check of Cyclo residues (for non-PRPs). Running cyclo twice on the same candidate (albeit in different h/w) is not exactly independent. And 80-bit cyclo will be too slow for practical use. But there is another way to do it. We can calculate 2^(N-1) (mod N) as (2^((N-1)/b)^b. Since this is the same computation, the final residue should be the same, but every intermediate state will be different. Hence, this computation sort of fulfills the same role as GIMPS's random rotation thing. We could do (2^((N-1)/b^r)^(b^r) for some small random r.

Clever, huh?

[Batalov]

The last operation x^b may be a bit tricky; the usual exponentiation relies on x being small: lots of squarings with some mul by x.
When x is as large as the whole residue, the long mul will need to be implemented.