20200816, 20:51  #1 
Aug 2020
2·5 Posts 
LucasLehmer Test for Fermat Numbers.
Here is a short paper by me on the LucasLehmer Test for Fermat Numbers with a short readable Theorem and an Algorithm which implements the LucasLehmer Test for the Fermat type Numbers.
Please read it and give some feedback! It is here in pdf attached! Allan Menezes 
20200816, 22:22  #2 
Aug 2020
2·5 Posts 
One can fashion a LL test using same similar code of prime95 for Mersenne Numbers that for Fermat Numbers too! The Pepin's test exists for Fermat Numbers and is deterministic and polynomial. This new LL test for Fermats is also deterministic and polynomial in running time of Order O(2^2n) for Fn=2^2^n+1 and is polynomial in Computing Space as well unlike the Pepins test.
Thank you! 
20200817, 09:00  #3 
"Jeppe"
Jan 2016
Denmark
176_{10} Posts 
If I understand correctly, this PARI method implements it:
Code:
LLFermat(m) = v=Mod(5,2^(2^m)+1);for(i=1,2^m2,v=v^22);v==0 Code:
Pepin(m) = v=Mod(3,2^(2^m)+1);for(i=1,2^m1,v=v^2);v==1 /JeppeSN 
20200817, 15:10  #4 
Aug 2020
2×5 Posts 
Yes they are the same time complexity. But it would be perhaps easier to modify Prime95 for the LL test rather than the Pepin test. At least thats what i hoped, So we could hunt for both Mersenne Primes and Fermat Primes. But in the algorithm for LL for Fermat number i have included a little a bit of factorization code by gcd which would make the LL longer but would also help in factoring Fermat Composites.
Allan 
20200817, 18:50  #5 
Einyen
Dec 2003
Denmark
3,253 Posts 
It is not really feasible since Fermat numbers get so incredibly big very fast, much faster than Mersenne numbers.
The smallest Fermat number with status unknown is F33 = 2^{2^33} + 1 = 2^{8589934592} + 1 This is ~82 times as many digits (NOT 82 times larger) as the current wave front of GIMPS. No computer or GPU can finish this within many years, and that is just the first unknown number. The next one F34 has twice as many digits as F33 and so on for each number. 
20200817, 20:57  #6 
∂^{2}ω=0
Sep 2002
República de California
13×29×31 Posts 
Thanks to the OP for sharing this interesting work, even if it offers no obvious computational advantage. As ATH notes, the Fermats are so sparse that no large distributedcomputing effort a la GIMPS is useful for them.
Codewise: my Mlucas code can handle either kind of modulus  both Mersennes and Fermats share the same core complexFFTbasedconvolution main code, but have specialized routines for the FFT pass bracketing the dyadicmul step between end of the fwdFFT and start of the invFFT, as well as specialized DWTweight/unweight and carry propagation routines. Mersennes want a realdata FFT so the dyadcmul step needs extra work to fiddle the complexFFT outputs to realdata form, do the dyadicmul, then fiddle real>complex in preparation for the iFFT. That adds ~10% overhead for Mersennes vs Fermats. The DWT+carry steps are similarly modulusspecialized because in the Fermat case we have 3 key differences vs Mersenne: 1. In the powerof2 transformlength case we need no Mersennestyle IBDWT, because the transform length divides the exponent, i.e. we can use a fixed base (2^16 makes the most sense for doublebased FFT and Fermats up to ~F35). If n = odd*2^k is not a power of 2  which is useful for smaller Fermats because we can squeeze more than 16 bits per input word into our FFT  we can use a Mersennestyle IBDWT, but there is a simplification in that the IBDWT weights repeat with period length [odd]. 2. Fermatmod needs an acyclic convolution, which means an extra DWT layered atop any in [1] in order to achieve that. 3. As described in the famous 1994 CrandallFagin IBDWT paper, Fermatmod arithmetic is most efficiently effected using a socalled "rightangle transform" FFT variant, which leads to a different way of grouping the residue digits in machine memory. Looking ahead a few years, I've discussed the feasibility of porting my Fermatmod custom code to Mihai Preda's (with major contributions from George Woltman) gpuOwl program with Mihai and George, and there would appear few hurdles aside from timeforcodeanddebug: gpuOwl uses the same kind of underlying complexFFT scheme as Mlucas. Running such a code on some cuttingedge GPU of a few years hence would appear the most feasible route to doing F33, though before running a Pepin test on that monster we'd want to do some *really* deep p1, say a stage 1 run for ~1 year on the fastest hardware available, and should that yield no factor (as we would expect) the resulting stage 1 residue could be made available for a distributed stage 2 effort, multiple volunteers doing nonoverlapping stage 2 prime ranges for, say, another year. 
20200826, 10:33  #7 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2^{2}·5·17·29 Posts 
I downloaded the PDF and looked into it, but I stopped after the first paragraph, and I deleted it, when I read that Fermat numbers are \(F_m=2^{2^m1}+1\).
Last fiddled with by LaurV on 20200826 at 10:38 Reason: \TeX ing it 
20200926, 01:55  #8 
Aug 2020
2×5 Posts 
Sorry an obvious typo in the document. I think we all know the definition of a Fermat Number Fn. If you do not here it is. A Fermat Number is Fn=2^2^n+1

20200926, 15:46  #9 
Sep 2009
4256_{8} Posts 
Would it work for GFNs, b^2^n+1 where b is an arbitrary base? There are enough possible GFNs that there should be some interesting cases small enough to test in a reasonable time.
Chris 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
LucasLehmer test  Mathsgirl  Information & Answers  23  20141210 16:25 
proof the lucas lehmer test  kurtulmehtap  Math  13  20091002 12:12 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
LucasLehmer Test proof  alpertron  mersennewiki  16  20060318 07:23 