Project description

The goal of GFN-MEGA project series is to find a MEGA prime for each GFN exponent, until software limits allows. MEGA Primes for GFN-17 and above were found or being searched on PrimeGrid. MEGA Primes for GFN-16 and GFN-15 were already found in these series. Now it's a time for GFN-14 MEGA, GFN-13 MEGA and so on. Last project in the series (when we hit software and math limits) is not determined yet, it can be either GFN-12 MEGA either GFN-11 MEGA.

These projects are exactly the same as previous GFN-15 project, so for detailed description and instructions please read top post in GFN-15 MEGA thread: https://www.primegrid.com/forum_thread.php?id=9198 . Everything is the same except:

GFN-14 MEGA:

• This is a GFN-14, so we're looking for MEGA Prime in form b¹⁶³⁸⁴+1
  
• Search will be started from b_min = 10841645805132531666786792405311319418846637043199917731144080
  
• Project name (for app_config.xml) is gfn14_mega
  

GFN-13 MEGA:

• Prime have form b⁸¹⁹²+1
  
• Search will be started from b_min = 117541283763947820803514936063599937165870515987063348437723855381224452611844232886228245901292532817349347812678728888242
  
• Project name (for app_config.xml) is gfn13_mega
  

GFN-12 MEGA:

• Prime have form b⁴⁰⁹⁶+1
  
• Search will be started from b_min = 138159533888....097738460 (very long, 245 digits)
  
• Project name (for app_config.xml) is gfn12_mega
  

GFN-11 MEGA:

• Prime have form b²⁰⁴⁸+1
  
• Search will be started from b_min = 190880568043....910259838 (very long, 489 digits)
  
• Project name (for app_config.xml) is gfn11_mega
  

Duration of all projects will follow same rules as GFN-15 MEGA - one month after prime will be found. Minimal duration will be 3 months (even if prime will be found faster).

Note that running LLR multithreaded significantly improves performance of these tasks. Using 4 cores per task is usually a good start. Using more cores may lead to worse overall perfomance because penalty of threads synchronization rises with number of cores, but your mileage may vary. Instructions are in the GFN-15 thread mentioned above.

For new users, please note once again that this is not a PrimeGrid project. It's running on separate server. Instructions to join are in the post mentioned above.

Current project status

GFN-14 MEGA: (completed)
2020-12-05: Project started
2020-12-17: First GFN14-MEGA Prime found
2021-03-05: Work loading stopped, cleanup started.
2021-04-13: Last task returned, project completed at b_min+600000, 2 primes found.

GFN-13 MEGA: (completed)
2021-03-27: Project started
2021-04-03: First GFN13-MEGA Prime found
2021-06-27: No new work will be loaded after this date
2021-07-30: Last task returned, project completed at b_min+600000, 5 primes found.

GFN-12 MEGA: (completed)
2021-07-26: Project started
2021-08-03: First GFN12-MEGA Prime found
2021-10-26: No new work will be loaded after this date
2021-11-13: Last task returned, project completed at b_min+600000, 4 primes found.

GFN-11 MEGA: (completed)
2022-03-02: Start of project
2022-03-24: First GFN11-MEGA Prime found
2022-06-02: No new work will be loaded after this date
2022-06-11: Last task returned, project completed at b_min+900000, 3 primes found.

Good luck and happy crunching!


Unproven and unreported primes

The test we're running on Boinc only checks for "probable prime" status. Although it's almost impossible for PRP of such size to be a "false positive", we must get strong mathematical proof of primality anyway. Any number we found must be tested using second algorithm, which gives an exact answer, is it a prime or not.

A key point of this algorithm is that base must be factorized at least on 33%. It became a problem starting from GFN12-MEGA, where base is 245 digits long. We were lucky to factorize bases of first two primes quickly, but third and fourth bases were hard.

Unfactorized cofactors of bases will be posted here. On my side, most of these numbers received at least 21000 GMP-ECM curves at B1=110M, which is (according to GMP-ECM predictions) should be enough to find a factor up to 55 digits long (i.e. we may consider that this number has no factors of 55 digits or less). Exceptions are noted in description of corresponding number.

Numbers are posted in "bc" format (split on few lines, trailing backslash added to mark continuation).

1. GFN12-MEGA prime #3, by "PDW", at b_min+264748, 225 digits in cofactor

Looking forward to it! Thanks Stream for all your amazing effort :D

A misconfiguration of LLR2 parameters (they were tweaked in special way for more efficient processing of GFN tests) caused invalid tasks to be sent until (estimated) 15:00 UTC. These tasks cannot complete, they will fail during final "checkpoint compression" phase with error message "proof.xxx is missing or corrupt".

In most cases affected tasks should be aborted automatically when one of tasks completes and your computer connects to the server. If you don't wish to wait and you still have tasks sent before 2020-12-05 15:00 UTC (check "Sent" field in your list of tasks on the server), it's recommended to abort these tasks manually because they just will consume CPU time and fail.

Update: you can just press "Update" button in Boinc client to force connection to server, and all affected tasks will be aborted.

Here is a bit of probabilities.
The expected number of GF primes in [b_min; b_min + d] (where b_min >> d) is C_n · d / (2ⁿ log b_min).
The mean gap between two primes is (#primes = 1) Δb = log b_min · 2ⁿ / C_n.
With mega-numbers log b_min · 2ⁿ = log 10⁹⁹⁹⁹⁹⁹ = 2302582.79.
For GFN-14, we have C₁₄ = 8.009684535 then Δb = 287475.

The range was sieved to p_max = 36·10¹⁸. The sieve removed 80% candidates.
If Δcand is the number of candidates for one prime, we have Δcand = (Δb / 2) · 20% = 28747.

Note that we could have used the estimate Δcand = e^-γ log N / log p_max = 0.5614594836 x 2302582.79 / 45.03 = 28710.

The likelihood of success is L = 1 - e^-λ where λ = #cand / Δcand.
L = 25%, #cand = 8264,
L = 50%, #cand = 19912,
L = 75%, #cand = 39824,
L = 97%, #cand = 100733.

Here is a bit of probabilities.
The expected number of GF primes in [b_min; b_min + d] (where b_min >> d) is C_n · d / (2ⁿ log b_min).
The mean gap between two primes is (#primes = 1) Δb = log b_min · 2ⁿ / C_n.
With mega-numbers log b_min · 2ⁿ = log 10⁹⁹⁹⁹⁹⁹ = 2302582.79.
For GFN-14, we have C₁₄ = 8.009684535 then Δb = 287475.

The range was sieved to p_max = 36·10¹⁸. The sieve removed 80% candidates.
If Δcand is the number of candidates for one prime, we have Δcand = (Δb / 2) · 20% = 28747.

Note that we could have used the estimate Δcand = e^-γ log N / log p_max = 0.5614594836 x 2302582.79 / 45.03 = 28710.

The likelihood of success is L = 1 - e^-λ where λ = #cand / Δcand.
L = 25%, #cand = 8264,
L = 50%, #cand = 19912,
L = 75%, #cand = 39824,
L = 97%, #cand = 100733.

1000 tasks/day, 4000 validated
Likelihood of success before Great Conjunction Challenge is
1 - exp(-(4000 + 11000) / 28747) = 40% !!!

It's really interesting to see how both 'normal' and 'mega' GFN14 are being tested at the same time...
____________
My lucky number is 6219*2^3374198+1

A quick success!

On 17 Dec 2020, 12:38:09 UTC, PDW found a prime 10841645805132531666786792405311319418846637043199917731150000^16384+1 (at b_min+5920). Congratulations!

As you can see, b_min is very small. If workunit wasn't timed out and aborted twice before PDW grabbed it, the prime could be found on the first day of the search.

Main goal of project is reached, first GFN-14 MEGA Prime found. Project will be active and new work will be loaded for 3 months since day of the start, until 05 March 2021.

Congrats PDW! Well done :)
____________
My lucky number 1059094^1048576+1

Not sure if I find it relevant to continue until March when the prime has already been found.

Thank you, there's still that obligatory second one left to find, just waiting for stream to post that it is unlikely to happen first !

New prime at b_min+167796!

https://primes.utm.edu/primes/page.php?id=131496

Congratulations Pavel!

The GFN-14 MEGA prime search is close to planned finish, which will happen on March 05. After this day, no new work will be loaded and project will be shut down after cleanup of all currently loaded and pending tests. The goal of project has been successfully reached, finding 2 mega primes, and few last weeks project was run mostly for peoples who have own goals or need WuProp hours.

GFN-14 MEGA search will be replaced by next project in sequence, GFN-13 MEGA search. It's b_min will be much bigger, but still manageable and, I hope, we will be able to factor resulting b to prove that number is prime (otherwise, we can get mathematically proof only for PRP).

To avoid conflict with PrimeGrid activities (upcoming SoB challenge on March 14 and attempt to finish DIV project before SoB challenge), start of GFN-13 project will be delayed. Estimated start date of new project will be Saturday, March 27. It's possible that GFN-14 MEGA will be completely cleaned up before this point and no any GFN-MEGA tasks will be available for few days. In this case, feel free to join "LLR2 testing" subproject which is currently double-checking suspicious (single-residue) PrimeGrid PPS-MEGA tests and already found one missing PPS-MEGA prime.

GFN-13 MEGA will be started March 27, 2021 at 09:00 UTC

There are not much differences between GFN-14 MEGA and GFN-13 MEGA, so I combined all GFN-MEGA projects into single forum thread and wrote common top post.

GFN-13 MEGA task duration and granted credit will be very close to GFN-14 MEGA. The only difference is an application name for app_config.xml - it'll be gfn13_mega

Like in previous projects in series, mutlithreading (via app_config.xml) is highly recommended for most CPUs, but its efficiency is limited to 4 cores (i.e. using more then 4 cores will not give you noticeable boost, and extra cores will mostly stay idle).

GFN-13 MEGA will be started March 27, 2021 at 09:00 UTC

There are not much differences between GFN-14 MEGA and GFN-13 MEGA, so I combined all GFN-MEGA projects into single forum thread and wrote common top post.

GFN-13 MEGA task duration and granted credit will be very close to GFN-14 MEGA. The only difference is an application name for app_config.xml - it'll be gfn13_mega

Like in previous projects in series, mutlithreading (via app_config.xml) is highly recommended for most CPUs, but its efficiency is limited to 4 cores (i.e. using more then 4 cores will not give you noticeable boost, and extra cores will mostly stay idle).

GFN-13 MEGA will be started March 27, 2021 at 09:00 UTC

There are not much differences between GFN-14 MEGA and GFN-13 MEGA, so I combined all GFN-MEGA projects into single forum thread and wrote common top post.

GFN-13 MEGA task duration and granted credit will be very close to GFN-14 MEGA. The only difference is an application name for app_config.xml - it'll be gfn13_mega

Like in previous projects in series, mutlithreading (via app_config.xml) is highly recommended for most CPUs, but its efficiency is limited to 4 cores (i.e. using more then 4 cores will not give you noticeable boost, and extra cores will mostly stay idle).

Is this correct to make them use 4 cores? I'd been running single core on the 14s, I didn't know you could multithread them (shouldn't it default to 4 if that's best, like the main primegrid ones do?):

<app_version> <app_name>gfn13_mega</app_name> <plan_class>mt</plan_class> <avg_ncpus>4</avg_ncpus> </app_version>

New LLR2 application (LLR2 version 1.1.1 2021-02-04, Boinc version 116) is installed (Linux only, Windows will be updated soon)

This version includes major update of gwnum (version 30.4) so it may contain unpredictable bugs (although certification will catch any possible calculation errors). Please report here if you'll notice something unusual.

New version of gwnum has improved multithreading support - is about 10% faster on GFN-MEGA tests in multithreaded setup. Speed of single-code tests is unchanged. Time per iteration on my home PC (4 cores):

Old version: 930 ms/bit
New version: 825 ms/bit

CPU usage also increased from 3.1 to 3.5 (on 4 cores).

Speed of Proth testing, most probably, was not changed, but I didn't tested much.

Also this version should read checkpoint files for tests with b <> 2 significantly faster. This improves speed of checkpoint compression at the end of test, but only in cases when LLR was restarted and checkpoint data had to be read again from disk. (It'll not affect cases when test was run continuously from beginning to end without interruption, because in this case checkpoint data is kept cached in memory and no need to read anything). A function which reads checkpoint data was completely rewritten by gwnum author, it may contain any new bugs, so please report everything unexpected.

Yes, we have a prime! And it's proven. The base was successfully factorized in about a hour using yafu, and prime was proven by pfgw.

It seems to be a first T5K prime for mmonnin. Congratulations! mmonnin, please follow instructions I sent you in GFN Server PM. In short, the best way is just to edit your prime reporting preferences here on PrimeGrid.

The GFN-13 MEGA Prime is on T5K.

https://primes.utm.edu/primes/page.php?id=132212

The GFN-13 MEGA Prime is on T5K.

https://primes.utm.edu/primes/page.php?id=132212

And we have second GFN-13 MEGA prime! Congratulations PDW!

Since T5K site is currently under maintenance and reporting is broken, prime was not reported yet. All what I can say now is that base was factorized without any problems in a fraction of a second using YAFU, it had few small and one very big factor (109 digits).

Congrats PDW! ...and could be the 1000th Mega recorded on T5K too? ;)
____________
My lucky number 1059094^1048576+1

Wow! Third GFN-13 MEGA prime, very close to previous one! Congratulations [SG-FC] dingdong! Very lucky find - according to stats, this user currently did only 64 tasks!

Again, base was factorized without problems. It had only two factors, first very small and second everything else.

Does the "LLR2 testing" subproject do multithreading aswell?

Thanks, shall I use 3 threads as per the MEGA?

And is this right?

Two pending primes reported, status page updated - it'll now show links to T5K pages.

Another prime found! What a productive N, 4 primes in just a 350K range! (all previous searches were stopped with just two primes)

Congratulations LCB001!

And we have a fifth prime! Unbelievable! Congratulations PDW, it's a his second prime in GFN-13-MEGA project!

Three months passed, no new work will be loaded, cleanup of remaining work started. Currently work is loaded up to b_min+600000, and about 7000 tasks left. Participation is varying, with current rates cleanup may take from 3 to 6 weeks.

GFN-13 MEGA is coming to the end. About 4 days of new work left at current rate. After that, only occasional resent tasks will be available.

Next project, GFN-12 MEGA, will be started shortly after the end of PrimeGrid challenge. Exact date will be announced later.

We're ready to continue!

GFN-12 MEGA will be started on Monday, July 26, at 09:00 UTC.

It should be not much difference on client side. All GFN-MEGA tasks have same FFT size and same runtime. Multithreading is recommended.

It's not decided yet, but this project can be last in the series. To prove found number as a prime, we must factorize 'b'. In GFN-12 MEGA, 'b' is 245 digits long. Factorizing such number will be quite a challenge. 'b' for GFN-11 MEGA will be two times longer.

Well, it didn't take long...

First GFN-12 MEGA prime found by PDW!

(Not surprised at all, considering that he is #1 in charts :-)

Congratulations!

Additional information will be posted later, when I'll finish factorization of the base and verification of the prime.

It sounds like you believe the factorization of b will finish.

Edit 2: Also see the b is submitted as http://factordb.com/index.php?id=1100000002638706977.

If we are unlucky and hit a base with two prime factors over 100 decimal digits, then it will be extremely hard to factor. I think it was lucky that second-largest prime factor had no more than 29 digits. /JeppeSN

And second prime, at b_min+136684, was found by robish. Congratulations with this well-deserved discovery! (Robish is #2 in project stats).

No problem with factorization again - less then two seconds of ECM testing. Are we still extremely lucky?

How long would the primality test take if the base isn't factored?

With numbers that size it isn't unlikely that you're left with a 190 or more digit co-factor that isn't acessible by ECM. And NFS would take more than a year on a single computer.

On the other hand, I think highly composite bases are more likely to produce a prime within a given range. On yet another hand, they could have a lot of small, 10 digit factors and still have a 210 digit co-factor that's very hard to factor.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000

The third prime is found! Congratulations PDW (again :)

Factorization and verification is still in progress. The prime will be visible when done (or considered to be impossible)

NM. I see my answer is in the OP. D'oh!
____________
Reno, NV

The third prime is found! Congratulations PDW (again :)

Factorization and verification is still in progress. The prime will be visible when done (or considered to be impossible)

Over eight days have passed? Maybe we really found a prime whose base is "impossible" to factor sufficiently? /JeppeSN

Over eight days have passed? Maybe we really found a prime whose base is "impossible" to factor sufficiently?

(Thankyou for your defn of semiprimes - only 2 primes - do the primes need to be only used once? I mean as an example 2 x 3 vs 2 x 2 x 3)

The definition says two primes when counted with multiplicity. So 2×3 and 2×2 and 3×3 would all be semiprimes, but 2×2×3 and 2×3×3 are not since for this purpose they have three prime factors (2, 2, 3; respectively 2, 3, 3).

The semiprimes used in RSA must have distinct prime factors. The two primes should not be extremely close to each other (then people could guess them, starting from the square root of the semiprime).

/JeppeSN

Yes I think I may understand why you wouldn't choose 2 primes close together for RSA.
I need more confirmation as what a semi-prime is.
Right now, I think it would be only 2 primes multiplied together and they can be the same prime? Sorry this probably is dogged stupidity.

I have several GFN-12 MEGA Prime task results that won't upload. A batch from 20 August has been stuck for almost a week. I tried crunching a new batch yesterday to "flush them through," but now those results are stuck too:

15756 PRIVATE GFN SERVER 9/5/2021 4:32:06 PM Started upload of llr2_1717963_qyn8br_765778086_r1399372121_7 15757 PRIVATE GFN SERVER 9/5/2021 4:32:06 PM Started upload of llr2_1717963_qyn8br_765778086_r1399372121_8 15758 PRIVATE GFN SERVER 9/5/2021 4:32:07 PM Project communication failed: attempting access to reference site 15759 PRIVATE GFN SERVER 9/5/2021 4:32:07 PM Temporarily failed upload of llr2_1717963_qyn8br_765778086_r1399372121_7: transient HTTP error 15760 PRIVATE GFN SERVER 9/5/2021 4:32:07 PM Backing off 05:00:33 on upload of llr2_1717963_qyn8br_765778086_r1399372121_7

Any clue as to why I can connect to download WUs, but not connect to upload results?

Fourth prime found by Dr Who Fan! Congratulations! Incredible luck, considering that he did only 93 tasks at the moment I'm writing this post.

The base resisted quick factorization, but I'll do more ECM testing at least for a week.

I'm also running it in background using YAFU ECM, it's slow because YAFU is running ECM single-threaded, and I didn't understand is it possible to make it multithreaded or not. Anyway, YAFU (if I understood its output correctly) should reach optimal point for 50-digits factor within next week.

I tried to learn NFS, and have cado-nfs server up and running. Everything is on default settings, using 230-digits profile supplied with cado. Look like I can build a polynomial in reasonable time even with my office computers, but have no idea yet how long sieving phase will take.