20201002, 18:26  #1 
Nov 2014
2^{3}×3 Posts 
PRP for F33?
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?
Last fiddled with by gLauss on 20201002 at 18:38 
20201002, 19:05  #2 
Einyen
Dec 2003
Denmark
3,037 Posts 
It is ~8.6 times as many iterations as the 1G exponent, but it would require a much much larger FFT size, so each iteration would take much much longer. Not sure how much longer but total running time is >50 times longer than the 1G exponent and probably a lot more.
Another huge problem is that there are currently no programs that can do a large enough FFT size for a this number. I think the largest currently is CUDALucas 65536K (64M) FFT which is "only" enough for ~1.14G exponents. Last fiddled with by ATH on 20201002 at 19:08 
20201002, 21:05  #3  
"Curtis"
Feb 2005
Riverside, CA
2×2,339 Posts 
Quote:
Once Ernst or Mihai or George extend the software to handle it, someone may well take it on but at 89x the time estimate you gave, you should see that it's not obvious that it needs doing on current hardware. 

20201002, 23:28  #4  
Mar 2019
90_{16} Posts 
Quote:


20201003, 00:26  #5 
"Curtis"
Feb 2005
Riverside, CA
2×2,339 Posts 
Sure double the exponent, double the FFT size. Then add a little bit more, say 10% extra per doubling.
forumite ewmeyer, the developer of cudalucas and mlucas, has done the largest Fermat test that I know of. See https://mersenneforum.org/showthread.php?t=21544 for details of his efforts to run F30. I believe he used 32768K FFT size for F30, so something like 262144K or whatever the next step larger would be sufficient to test F33. F30 took a really long time, though I'm not seeing F33 as a reasonable proposition until GPUs are an order of magnitude faster. 
20201003, 03:37  #6  
Einyen
Dec 2003
Denmark
3,037 Posts 
Quote:
I have not checked FMA FFT recently in Prime95, but it goes to at least 50M. 

20201003, 05:07  #7  
Romulan Interpreter
Jun 2011
Thailand
5^{2}·7·53 Posts 
Quote:
Last fiddled with by LaurV on 20201003 at 05:08 

20201003, 09:39  #8 
Nov 2014
2^{3}·3 Posts 
Thanks for the answers. I now understand why it wasn't done before:

20201003, 14:01  #9  
Einyen
Dec 2003
Denmark
3,037 Posts 
Quote:
Since Ernst got an iteration time on F33, Mlucas must have big enough FFT to handle it, and now that I check I can see it goes to at least 240M FFT (245760K) in an old selftest I did on Mlucas. But the 2 other points are still valid, it takes way too long and it cannot be distributed to many computers. Last fiddled with by ATH on 20201003 at 14:01 

20201003, 18:15  #10 
Aug 2002
Buenos Aires, Argentina
17×79 Posts 
Before even thinking on performing the primality check of F33, a lot more trial factoring is needed and then someone has to run P1.

20201003, 18:38  #11 
Apr 2010
Over the rainbow
2×5×11×23 Posts 
recently , I factored (PM1)a 535 M exponent with PM1, the FFT lenght was "fftlength":31457280 aka 30720k.
Code:
[Tue Sep 1 02:03:45 2020] FFTlen=30720K, Type=3, Arch=4, Pass1=1536, Pass2=20480, clm=4 (3 cores, 1 worker): 67.53 ms. Throughput: 14.81 iter/sec. FFTlen=30720K, Type=3, Arch=4, Pass1=1536, Pass2=20480, clm=2 (3 cores, 1 worker): 66.36 ms. Throughput: 15.07 iter/sec. FFTlen=30720K, Type=3, Arch=4, Pass1=1536, Pass2=20480, clm=1 (3 cores, 1 worker): 75.09 ms. Throughput: 13.32 iter/sec. FFTlen=30720K, Type=3, Arch=4, Pass1=2048, Pass2=15360, clm=4 (3 cores, 1 worker): 64.08 ms. Throughput: 15.61 iter/sec. FFTlen=30720K, Type=3, Arch=4, Pass1=2048, Pass2=15360, clm=2 (3 cores, 1 worker): 64.12 ms. Throughput: 15.60 iter/sec. FFTlen=30720K, Type=3, Arch=4, Pass1=2048, Pass2=15360, clm=1 (3 cores, 1 worker): 66.83 ms. Throughput: 14.96 iter/sec. 