20040223, 21:10  #1 
Feb 2004
23 Posts 
What are the Primality Tests ( not factoring! ) for Fermat Numbers?
Hi
I have been dealing with factors of fermat numbers F12,F13,F14 I know that primality status of some fermat numbers F33,F34... are still unknown. Many are working on factoring but not a long way has been travelled on primality check. As far as i know, best primality test is Pepin's Test (1877) which is quite old in my opinion. Of course Proth's theorem is like a generalization of Pepin's test with unrestricting the base. Here is my question, is there any more efficient new algorithms to test primality of fermat numbers, or can you think any sort of improvements on this subject. Currently, Pepin's Test deals with the whole fermat number in modular arithmetic(2^2^N). May be someone can show up with more iterations but dealing with just the exponent of fermat number (which is 2^N) ??? 
20040223, 21:43  #2 
Sep 2002
1226_{8} Posts 
Aren't Fermat numbers F5 and above, all composite ?

20040223, 21:51  #3  
Nov 2003
3·5·11 Posts 
Quote:
Last fiddled with by nfortino on 20040223 at 21:52 

20040226, 07:49  #4 
Mar 2003
3^{4} Posts 
3^[(Fn1)/2] = (1) mod Fn
Is this Pepin's test? 
20040226, 12:10  #5  
Mar 2003
51_{16} Posts 
Quote:


20040524, 14:56  #6  
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
Quote:
And like Mersennemod, Fermatmod multiply permits a fast DWTbased algorithm. Re. a way of proving the number while dealing only with quantities the size of the exponent  that's what trial factoring does. But if that fails to turn up a small factor, the only way we know of to establish the character of such numbers is to resort to methods that use fullblown multiplies modulo the number being tested. 

20040526, 21:56  #7 
Feb 2004
France
929 Posts 
Why not using LucasLehmer test ?
I think LucasLehmer test also works for Fermat numbers.
Why not using it, starting with 5 ? Examples: F2=2^2^2+1=2^4+1=17 u0=5 u1=5^22=6 mod 17 u2=6^22=0 mod 17 F3=2^2^3+1=2^8+1=257 u0=5 u1=5^22=23 u2=23^22=+/13 mod 257 u3=13^22=+/90 mod 257 u4=90^22=+/126 mod 257 u5=126^22=+/60 mod 257 u6=60^22=0 mod 257 
20040526, 22:14  #8 
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
Interesting  it also gives 0 for F4, but not for F5.
There might be something there (though it would require more than just numerical evidence to validate or disprove the algorithm), but even if we could do an LLstyle style test on the Fermats, it would be no faster than the Pe'pin test. 
20040526, 23:05  #9 
"Phil"
Sep 2002
Tracktown, U.S.A.
45F_{16} Posts 
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 N1. 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! 
20040527, 01:19  #10 
May 2004
2·37 Posts 
Proof Of Infinitude Of Prime Fermat Numbers
I think that there are infinitely many Fermat primes, even Fermat primes are rare and there is a slim or no chance of finding another Fermat prime. Can you draw a complicated shape, instead of a triangle, pentagon, 17gon, 257gon and 65537gon to discover a Fermat prime?
I mean, go search for very large Fermat primes, 2^(2^n)+1 for n greater than 32, other than the first five Fermat primes. 
20040527, 02:37  #11 
Dec 2003
Hopefully Near M48
2·3·293 Posts 
Last fiddled with by jinydu on 20040527 at 02:40 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pépin tests of Fermat numbers beyond F24  ewmayer  Computer Science & Computational Number Theory  83  20220701 22:35 
Use Pepin's Tests for proving primality of Mersenne numbers ?  T.Rex  Math  12  20160403 22:27 
Proof of Primality Test for Fermat Numbers  princeps  Math  15  20120402 21:49 
The fastest primality test for Fermat numbers.  Arkadiusz  Math  6  20110405 19:39 
Two Primality tests for Fermat numbers  T.Rex  Math  2  20040911 07:26 