mersenneforum.org P.I.E.S. - Prime Internet Eisenstein Search
 Register FAQ Search Today's Posts Mark Forums Read

 2015-02-08, 06:54 #46 axn     Jun 2003 3·17·101 Posts 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
 2015-02-08, 07:12 #47 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·4,787 Posts 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.
2015-02-08, 14:34   #48
axn

Jun 2003

3×17×101 Posts

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.
Attached Files
 cyclosv0.5.zip (80.3 KB, 229 views)

 2015-02-08, 18:31 #49 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·4,787 Posts 192098^262144 - 192098^131072 + 1 is prime. (Cyclo on a K520 2311.0 sec., err=2.88e-02, 1385044 digits) Code: 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) Attached Thumbnails
 2015-03-08, 01:54 #50 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 256616 Posts 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 Phi5(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, Phi10(x)-1 has factors x and x-1 and one can be fully factored and the other >33.3% factored. Similar numbers have form Phi5(x) or Phi10(x), where x = { pq | pq-1 | pq+1 } (one form for each Phi5 and Phi10 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 < p2 to achieve the >33.3% proof.) P.S. Another one is Phi7(p) (i.e. p6+p5+p4+p3+p2+p+1), where p=5978493*2^150006-1. With 270979 decimal digits, it is a bit short of entering the UTM prime database. Last fiddled with by Batalov on 2015-03-11 at 06:04
 2015-05-06, 21:00 #51 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 225468 Posts Capt. Obvious warns the non-believers: 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. Attached Thumbnails
 2015-05-08, 16:04 #52 axn     Jun 2003 3·17·101 Posts 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
 2015-05-08, 17:07 #53 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×4,787 Posts 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.
 2015-05-09, 09:38 #54 axn     Jun 2003 3·17·101 Posts 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?
 2015-05-09, 15:40 #55 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×4,787 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Jwb52z Software 10 2013-01-30 01:09 MooooMoo Twin Prime Search 115 2010-08-29 17:38 Unregistered Information & Answers 5 2009-10-15 22:44 Kosmaj Riesel Prime Search 6 2006-11-21 15:19 Ferdy Software 3 2006-04-25 08:53

All times are UTC. The time now is 22:06.

Tue Oct 26 22:06:55 UTC 2021 up 95 days, 16:35, 1 user, load averages: 1.07, 1.11, 1.30