Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2020-08-16, 20:51   #1
Aug 2020

128 Posts
Post Lucas-Lehmer Test for Fermat Numbers.

Here is a short paper by me on the Lucas-Lehmer Test for Fermat Numbers with a short readable Theorem and an Algorithm which implements the Lucas-Lehmer Test for the Fermat type Numbers.
Please read it and give some feedback!
It is here in pdf attached!
Allan Menezes
Attached Files
File Type: pdf fermatlltest2.pdf (181.7 KB, 286 views)
amenezes is offline   Reply With Quote
Old 2020-08-16, 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!
amenezes is offline   Reply With Quote
Old 2020-08-17, 09:00   #3
JeppeSN's Avatar
Jan 2016

5·37 Posts

If I understand correctly, this PARI method implements it:
LLFermat(m) = v=Mod(5,2^(2^m)+1);for(i=1,2^m-2,v=v^2-2);v==0
The way I understand Pépin's test, is:
Pepin(m) = v=Mod(3,2^(2^m)+1);for(i=1,2^m-1,v=v^2);v==-1
So it looks like they are equally good.

JeppeSN is offline   Reply With Quote
Old 2020-08-17, 15:10   #4
Aug 2020

10102 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.
amenezes is offline   Reply With Quote
Old 2020-08-17, 18:50   #5
ATH's Avatar
Dec 2003

19×181 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 = 22^33 + 1 = 28589934592 + 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.
ATH is offline   Reply With Quote
Old 2020-08-17, 20:57   #6
ewmayer's Avatar
Sep 2002
República de California

2DEB16 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 distributed-computing effort a la GIMPS is useful for them.

Code-wise: my Mlucas code can handle either kind of modulus - both Mersennes and Fermats share the same core complex-FFT-based-convolution main code, but have specialized routines for the FFT pass bracketing the dyadic-mul step between end of the fwd-FFT and start of the inv-FFT, as well as specialized DWT-weight/unweight and carry propagation routines. Mersennes want a real-data FFT so the dyadc-mul step needs extra work to fiddle the complex-FFT outputs to real-data form, do the dyadic-mul, then fiddle real->complex in preparation for the iFFT. That adds ~10% overhead for Mersennes vs Fermats.

The DWT+carry steps are similarly modulus-specialized because in the Fermat case we have 3 key differences vs Mersenne:

1. In the power-of-2 transform-length case we need no Mersenne-style IBDWT, because the transform length divides the exponent, i.e. we can use a fixed base (2^16 makes the most sense for double-based 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 Mersenne-style IBDWT, but there is a simplification in that the IBDWT weights repeat with period length [odd].

2. Fermat-mod 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 Crandall-Fagin IBDWT paper, Fermat-mod arithmetic is most efficiently effected using a so-called "right-angle 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 Fermat-mod 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 time-for-code-and-debug: gpuOwl uses the same kind of underlying complex-FFT scheme as Mlucas. Running such a code on some cutting-edge 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 p-1, 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.
ewmayer is offline   Reply With Quote
Old 2020-08-26, 10:33   #7
Romulan Interpreter
LaurV's Avatar
"name field"
Jun 2011

101000001010012 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^m-1}+1\).

Last fiddled with by LaurV on 2020-08-26 at 10:38 Reason: \TeX ing it
LaurV is offline   Reply With Quote
Old 2020-09-26, 01:55   #8
Aug 2020

128 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
amenezes is offline   Reply With Quote
Old 2020-09-26, 15:46   #9
chris2be8's Avatar
Sep 2009

22·607 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.

chris2be8 is offline   Reply With Quote

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 2018-03-11 23:20
Lucas-Lehmer test Mathsgirl Information & Answers 23 2014-12-10 16:25
proof the lucas lehmer test kurtulmehtap Math 13 2009-10-02 12:12
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas-Lehmer Test proof alpertron mersennewiki 16 2006-03-18 07:23

All times are UTC. The time now is 19:46.

Mon Feb 6 19:46:37 UTC 2023 up 172 days, 17:15, 1 user, load averages: 1.60, 1.18, 1.07

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔