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)

???

Aren't Fermat numbers F5 and above, all composite ?

[QUOTE=dsouza123]Aren't Fermat numbers F5 and above, all composite ?[/QUOTE]

Probably, but that has not been proven. All Fermat numbers up to F32 have been shown to be composite (besides obviously F0-4), and other larger Fermat numbers have been shown to be composite by finding factors. As for Erasmus's question, Pepin's test is the best I heard of, and said to be the best on the Prime Pages.

3^[(Fn-1)/2] = (-1) mod Fn
Is this Pepin's test?

[QUOTE=Cyclamen Persicum]3^[(Fn-1)/2] = (-1) mod Fn
Is this Pepin's test?[/QUOTE]

Kinda Rabin-Miller test on base 3 =))) But here it is deterministic and explicit...

[QUOTE=Erasmus]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)

???[/QUOTE]

Pepin's test may be old, but its asymptotic complexity is the same as for a Mersenne of similar size, i.e. both are examples of numbers of special form (and which are not composite by construction, i.e. they do need to be tested) which permit as fast a deterministic primality test as is known.

And like Mersenne-mod, Fermat-mod multiply permits a fast DWT-based 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 full-blown multiplies modulo the number being tested.

Why not using Lucas-Lehmer test ?
 

I think Lucas-Lehmer 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^2-2=6 mod 17
u2=6^2-2=0 mod 17

F3=2^2^3+1=2^8+1=257
u0=5
u1=5^2-2=23
u2=23^2-2=+/-13 mod 257
u3=13^2-2=+/-90 mod 257
u4=90^2-2=+/-126 mod 257
u5=126^2-2=+/-60 mod 257
u6=60^2-2=0 mod 257

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 LL-style style test on the Fermats, it would be no faster than the Pe'pin test.

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!

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, 17-gon, 257-gon and 65537-gon 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.

There's already such a search going on.

[url]http://www.prothsearch.net/fermat.html#Summary[/url]