PRP for F33?

[kriesel]

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:

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 = 2³³ · 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.

[kriesel]

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.

[bbb120]

Originally Posted by gLauss

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

[retina]

Originally Posted by bbb120

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?

[bbb120]

Originally Posted by retina

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]

Originally Posted by retina

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 !

[bsquared]

Originally Posted by bbb120

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".

[mathwiz]

Originally Posted by bbb120

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...

[VBCurtis]

Originally Posted by bbb120

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.

[bbb120]

Originally Posted by bbb120

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]

Originally Posted by bsquared

Learn about "binary splitting".

what does binary splitting mean?
can you give more information about binary splitting ?