mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2020-10-05, 05:22   #12
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

5×1,019 Posts
Default

I've put together a long post at https://www.mersenneforum.org/showpo...65&postcount=6 with estimates of run times, memory requirements, disk space, etc.
In a nutshell, Mlucas could do the Pepin test at 512M fft length, but run time is much too long on normal hardware. ECM and P-1 software support for F33 may be a problem.

Following are comments by Ernst Mayer regarding appropriate further factoring for F33, quoted by permission:
Quote:
based on the TF-to-date and the massive memory needs of ECM, I think only a very deep p-1 attempt is warranted prior to starting the primality test. By deep I mean several years long, perhaps something like this:

Year 1: single fast GPU does deep stage 1. If no error-check mechanism a la Gerbicz is available for that, we'd want 2 separate machines doing identical-bounds stage 1s, to be able to cross-check residues.

Year 2: stage 1 residue gets distributed to multiple users/machines, each of which does one or more work units consisting of powering the stage1 residue to the primes in a given range and doing a gcd to check for a factor. The p-1 code would need to be specially tuned to minimize memory usage: each F33-mod residue is 4GB (in 16 bits/DP form), so we couldn't keep more than 3 such in a Radeon VII's working memory, for instance. I think 32GB is likely the absolute minimum HBM that will be needed for stage 2 work.

The first step should probably be to try p-1 on F31, which has a known factor found via TF: p = 46931635677864055013377, which has p − 1 = 233 · 3 · 13 · 140091319777, i.e. needs just a very shallow stage 1 but a deep stage 2 (or a stage 2 using just the largest factor of p-1, 140091319777) to reproduce via p-1.
The proper P-1 bounds remain to be determined. The run times from Ernst imply larger bounds than I used to estimate run times. I don't know of any software currently up to the task of P-1 factoring for F33.

Last fiddled with by ewmayer on 2020-10-07 at 22:29 Reason: Copied PM-regarding-p-1 material from Off Topic thread to here, to encourage discussion.
kriesel is online now   Reply With Quote
Old 2020-10-08, 20:56   #13
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

13E716 Posts
Default

Several questions occur to me related to the preceding. Hopefully the top programmers and number theorists and most knowledgable Fermat subproject participants will weigh in.

TF:
  1. How much TF is enough for F33?
  2. How is that determined?
  3. How much TF has been done?
  4. How to succinctly describe that?
ECM:
  1. What are the ECM memory requirements for differing bounds?
  2. Extrapolating https://www.mersenneforum.org/showpo...69&postcount=1 to F33 implies a save file of ~2GB.
  3. What ECM has been done relevant to F33?
  4. What is the incremental probability of a factor for another ECM curve?
P-1:
  1. What are suitable bounds for P-1 for F33?
  2. What is the penalty function in P-1 stage 2 run time like, for 15 or fewer buffers versus 30 or many more?
  3. What then is the required system memory, processor, etc for P-1? (I could bring dual-xeons & 128GB/system to bear.)
  4. Where's the Fermat-capable P-1 factoring software for such large numbers?
  5. Or is it to be developed specifically to suit each Fermat number's P-1 factoring task?
  6. If so, what and where is the best source to start from?
http://www.fermatsearch.org/download.php lists lots of software. It does not list P-1 software. It does not give limits of listed software.
kriesel is online now   Reply With Quote
Old 2020-11-10, 06:11   #14
bbb120
 
bbb120's Avatar
 
Feb 2019
China

1110112 Posts
Default

Quote:
Originally Posted by gLauss View Post
Hi,
first of all, sorry if this is a noob question. I am wondering why noone has proven the (non-)primality of F33 with PRP testing. It will be a huge task, but should be doable, shouldn't it?
  • F33 is as large as M8.589.934.591, or in the 8G range.
  • Someone has done a PRP Test for a 1G exponent
  • mersenne.ca reports 62.000 GHzd for F30
  • So a F33 PRP test will be around 8 times this, i.e. around half a million GHz Days.
  • An 8G number should easily fit in the RAM of a powerful computer, too.
So why is noone attempting this task? Of course it would require something like an Amazon c5.metal instance, but if I would be Ben Delo and pushing 50 million GHz Days in the last year, then I would use 1% of this in order to prove the compositeness of F33...
50 Trillion Digits of Pi
https://www.mersenneforum.org/showthread.php?t=25155
why we can calculate 50 trillion digits of Pi ,but cannot test a PRP test on F33,
F33 only has no more than 2700 billion digits
bbb120 is offline   Reply With Quote
Old 2020-11-10, 06:42   #15
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22×5×307 Posts
Default

Quote:
Originally Posted by bbb120 View Post
50 Trillion Digits of Pi
https://www.mersenneforum.org/showthread.php?t=25155
why we can calculate 50 trillion digits of Pi ,but cannot test a PRP test on F33,
F33 only has no more than 2700 billion digits
You can test F33 if you want to. But you need to have all surpassing patience.

The difference is the iteration count. Did you see how many iterations for PI? Compare that to F33. Now do you see why?
retina is offline   Reply With Quote
Old 2020-11-11, 00:37   #16
bbb120
 
bbb120's Avatar
 
Feb 2019
China

59 Posts
Default

Quote:
Originally Posted by retina View Post
You can test F33 if you want to. But you need to have all surpassing patience.

The difference is the iteration count. Did you see how many iterations for PI? Compare that to F33. Now do you see why?
F33=2^(2^33)+1=2^8589934592+1
(F33-1)/2=2^4294967296
3^((F33-1)/2)=-1(mod F33) <=> F33 is a prime number
it needs 4294967296 iterations

50 Trillion Digits of Pi,50*10^12,
15digits per iteration,itneeds 50/15*10^12=3.3333*10^12 iteration,
http://www.numberworld.org/y-cruncher/#Algorithms
bbb120 is offline   Reply With Quote
Old 2020-11-11, 00:45   #17
bbb120
 
bbb120's Avatar
 
Feb 2019
China

3B16 Posts
Default

Quote:
Originally Posted by retina View Post
You can test F33 if you want to. But you need to have all surpassing patience.

The difference is the iteration count. Did you see how many iterations for PI? Compare that to F33. Now do you see why?
according to prime number theorem , the probability of F33 is a prime only has
1/(2^33*log(2))=3.86723328252e-10, so it must be a composite number !
bbb120 is offline   Reply With Quote
Old 2020-11-11, 00:58   #18
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×859 Posts
Default

Quote:
Originally Posted by bbb120 View Post
50 Trillion Digits of Pi,50*10^12,
15digits per iteration,itneeds 50/15*10^12=3.3333*10^12 iteration,
http://www.numberworld.org/y-cruncher/#Algorithms
Learn about "binary splitting".

Last fiddled with by bsquared on 2020-11-11 at 00:58
bsquared is offline   Reply With Quote
Old 2020-11-11, 02:02   #19
mathwiz
 
Mar 2019

157 Posts
Default

Quote:
Originally Posted by bbb120 View Post
according to prime number theorem , the probability of F33 is a prime only has
1/(2^33*log(2))=3.86723328252e-10, so it must be a composite number !
Ok! Go find a factor, then...
mathwiz is offline   Reply With Quote
Old 2020-11-11, 02:04   #20
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

13×367 Posts
Default

Quote:
Originally Posted by bbb120 View Post
according to prime number theorem , the probability of F33 is a prime only has
1/(2^33*log(2))=3.86723328252e-10, so it must be a composite number !
By this logic, nobody ever wins the lottery. You can't be serious.
VBCurtis is offline   Reply With Quote
Old 2020-11-11, 02:33   #21
bbb120
 
bbb120's Avatar
 
Feb 2019
China

59 Posts
Default

Quote:
Originally Posted by bbb120 View Post
according to prime number theorem , the probability of F33 is a prime only has
1/(2^33*log(2))=3.86723328252e-10, so it must be a composite number !
1/(2^33*log(2))=1.679518074832116*10^-10
not 1/(2^33*log(2))=3.86723328252e-10(wrong caused by sogou pinyin)
bbb120 is offline   Reply With Quote
Old 2020-11-11, 02:34   #22
bbb120
 
bbb120's Avatar
 
Feb 2019
China

5910 Posts
Default

Quote:
Originally Posted by bsquared View Post
Learn about "binary splitting".
what does binary splitting mean?
can you give more information about binary splitting ?
bbb120 is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 10:57.

Fri May 7 10:57:39 UTC 2021 up 29 days, 5:38, 0 users, load averages: 3.04, 3.09, 3.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.