What are the Primality Tests ( not factoring! ) for Fermat Numbers?

[T.Rex]

Originally Posted by philmoore

Interesting, I checked up through F13 and the test worked every time. (Although the interesting thing isn't that it fails for most Fermat numbers, it's that it works only on F1, F2, F3, and F4.) I thought Lucas sequences were useful when you knew all the factors of N+1, whereas for Fermat factors, you know all the factors of N-1. Does anyone know enough about this to be able to figure out if the test is rigorous?

Tony, did you figure this out by numerical experimentation? Very nice!

Not exactly numerical experimentation.
I studied the S(n)=S(n-1)^2-2 function and I discovered some nice symmetries and relationships for Mersenne numbers. Since I saw the same
properties for Fermat numbers, I'm convinced (but no proof) that my formula:
u(0) = 5
u(N)=u(N-1)^2-2
Fn is prime <==> u(2^n-2) = 0 (mod Fn)
is correct for Fermat numbers.
I plan since years to spend time to describe what I found in order to ask people if it is some representation of well-known properties of (so complex)
Lucas numbers, or not.
I don't know if using FFT for testing the primality of Fermat numbers is faster than Pepin's test. But since there exist multi-threaded Mersenne test programs, it may help. Even the modulo Fn can be easily written.
Who could help about the Maths behind this ?
Tony

[jinydu]

Unfortunately, the smallest Fermat Number with unknown primality status (F33) has over 2.58 billion digits...

[akruppa]

In Williams P+1 factoring, whether your starting element s has order p+1 or p-1 depends on whether s^2-4 isn't or is a qudaratic residue (mod p). I believe the same is happening here.

For Mersenne numbers with odd exponent > 1 and s=4, 4^2-4=12=4*3 is a QNR, because 4 is trivially a QR and 3 is a QNR by quadratic reciprocity [2^(2*e+1)-1 == 1 (mod 3) which is a QR, and both are 3 (mod 4)], so 4*3 is a QNR (mod 2^(2*e+1)-1) and we'll properly conduct a p+1 primality test.

For Fermat numbers F_m, m>0, with s=5, s^2-4 = 21 = 3*7, 3 is a QNR (mod F_m) [as 2^(2^m)+1 == 2 (mod 3) is a QNR and F_m is not 3 (mod 4)], 7 is a QNR [as (2^(2^m)+1 == 3 or 5 (mod 7), both 3 and 5 are QNR (mod 7)], so 3*7 is a QR (mod F_m) and we get a p-1 primality test just like Pepin's test in (Z/ZF_m)*.

Alex

[ewmayer]

Originally Posted by T.Rex

I don't know if using FFT for testing the primality of Fermat numbers is faster than Pepin's test. But since there exist multi-threaded Mersenne test programs, it may help. Even the modulo Fn can be easily written.
Who could help about the Maths behind this ?
Tony

I think you're confusing the mathematical algorithms for verifying primality (LL and Pe'pin) with the algorithms (FFT and DWT) for efficiently effecting the large-integer modular multiplies that dominate the computational cost for these primality tests once the numbers being tested get big. FFT is simply a way (probably the fastest way known on modern microprocessors) to speedily effect large-integer multiplies, which can be shown to be nothing more than cyclic convolutions of the vectors of digits that the large input integers are broken into on the computer hardware (e.g. if you were doing a Fermat-mod multiply using a wordsize of 16 bits, that amounts to representing the input integer in base-2^16 form). The various flavors of the DWT all have the aim of further speeding the modmul by building the modular reduction directly into the fast transform used to effect the multiply. So one can use an FFT-based multiply for any kind of input number, whether or not a DWT exists (or better, has been found) for the number we are using as the modulus. Here are the key differences between Fermat and Mersenne-number moduli:

* Fermat are of form 2^n + 1, so require an acyclic (sometimes called "negacyclic") convolution if we are doing an implicit mod (i.e. a DWT). Unmodified FFT-based mul gives a cyclic convolution, but there is a well-known way to multiply the inputs by certain roots of unity (the DWT weights for acyclic convolution) so as to get an acyclic convolution as output. For Fermats it is most natural to use a power-of-2 wordsize (which yields a power-of-2 FFT length), but if a non-power-of-2 transform length is desired, one can layer a second set of DWT weights - the same type as used in the Crandall/Fagin Mersenne-mod DWT - on top of the acyclic-effecting ones to achieve this.

* Mersenne are of form 2^n - 1, so require a cyclic convolution if we are doing an implicit mod, thus no modification of the FFT is needed here. However, for Mersennes the exponent n is prime, so we can't break the input numbers into fixed-wordsize chunks. The C/F DWT allows us to break the inputs into variable word sizes (think of timekeeping, which breaks the day into a variable-base-representation: base-24 for hours and base-60 for minutes and seconds) in a systematic way so that the "folding" which occurs naturally in a (cyclic or negacyclic) convolution happens at the desired spot, i.e. at the (n)th bit of the underlying multiword integer without n needing to be a power of two or even to be composite.

For more details on this, here is a reference:

http://www.mersenneforum.org/attachments/pdfs/F24.pdf

Anyway, nice bit of work re. the LL-style test for Fermats - even if it gives no practical advantage over Pe'pin, a new mathematical method for testing primality of this class of numbers is always interesting to have, since it may yield new insights.

[T.Rex]

Hi EwMayer,
I need time for understanding all your explanations. I think I'm starting to understand the differences between the 2 computations.
About the proof, I think I have a proof (based on Ribenboim's book) about: [Fn Prime] ==> [Fn divides S(Fn-2)] , with: S0=5 , Sn=S(n-1)^2-2
I'm working on the reverse.

You seem to say it is a new Math result ? I would be very pleased if it's true. But I guess it is an old forgotten result.
Are there some more Mathematicians around that could help us about this ?
Tony

[T.Rex]

Hi,
Does someone has this book and can see if Mr Williams H. C. talks about using LLT for Fermat numbers ?
By the way, if you have read it, do you think it is a must-have book ? It seems very expensive.
Thanks.
Tony

[philmoore]

Yes, I have the book and will check this for you soon. (I'm in the middle of finals, so it may not be until next week.) It is a fascinating book if you find history of mathematics interesting. The book covers the entire history of primality testing, but focuses mainly on Lucas and Lehmer. Lucas is credited with the most significant insight in the history of primality testing, namely, that it is possible to prove a number prime without testing all possible factors. There is also an extensive discussion of pre-computer mechanical sieving devices. Three years ago, I attended the Lehmer conference in Berkeley, and several of Lehmer's sieves, including his bicycle chain sieve, were on display at the conference. Although the math is mostly available also in other sources, I did find Hugh Williams explanation of Lucas sequences quite clear. It is expensive, and I wonder if it can be obtained cheaper through sources other than the publisher. I remember that Powell's (in Portland Oregon) had copies a year or two ago for $80.

[T.Rex]

Hi Philmoore,
Thanks for your help! Yes, I think I will buy the book. I've visited the bookshops and the University library and they have very few things about Number Theory. (They may think people interested with such old Maths are crazy ...)
Tony

[T.Rex]

I have 95 % of a proof for my primality test for Fermat numbers based on the Lucas-Lehmer test, but I still don't know if it is or not kind of forgotten (because not useful) already known old maths.
Tony

[ET_]

Originally Posted by T.Rex

I have 95 % of a proof for my primality test for Fermat numbers based on the Lucas-Lehmer test, but I still don't know if it is or not kind of forgotten (because not useful) already known old maths.
Tony

Congratulations, Tony! Anyway, a proof can only be 100% or 0% correct... (just kidding)

You deserve admiration because, in case the proof was known, you rediscovered it on your own.

Luigi

[T.Rex]

Yes, you're right. It is 0 or 100 % !
In fact, I wanted to say that I had still to find solutions for proving the remaining parts. And sometimes, the 5% left may take very long ! or never succeed.
Now, I only have some details to prove, I think. Or maybe I'll find THE problem and failed to have a complete proof!
What is surprising me is that all books I've read (not so much) and all web-sites about Primality proving I've looked at say that this kind of test in only for N-1 numbers, like Mersenne numbers, not for N+1 numbers.
Even if I fail or if it is already known, it helped me to understand all the not explained and horrible details of the LLT that appear in the excellent Ribenboim's book. Also I found some small mistakes, I think.
Tony