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

Erasmus · 2004-02-23, 21:10

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)

???

dsouza123 · 2004-02-23, 21:43

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

nfortino · 2004-02-23, 21:51

Quote:

Originally Posted by dsouza123

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

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.

Cyclamen Persicum · 2004-02-26, 07:49

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

Cyclamen Persicum · 2004-02-26, 12:10

Quote:

Originally Posted by Cyclamen Persicum

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

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

ewmayer · 2004-05-24, 14:56

Quote:

Originally Posted by 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)

???

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.

T.Rex · 2004-05-26, 21:56

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

ewmayer · 2004-05-26, 22:14

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.

philmoore · 2004-05-26, 23:05

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!

Terrence Law · 2004-05-27, 01:19

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.

jinydu · 2004-05-27, 02:37

There's already such a search going on.

http://www.prothsearch.net/fermat.html#Summary

2004-02-23, 21:10	#1
Erasmus 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) ???

2004-05-26, 21:56	#7
T.Rex Feb 2004 France 13·73 Posts	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

2004-05-27, 01:19	#10
Terrence Law May 2004 112₈ 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, 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.

2004-05-27, 02:37	#11
jinydu Dec 2003 Hopefully Near M48 3336₈ Posts	There's already such a search going on. http://www.prothsearch.net/fermat.html#Summary Last fiddled with by jinydu on 2004-05-27 at 02:40

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Pépin tests of Fermat numbers beyond F24	ewmayer	Computer Science & Computational Number Theory	89	2023-06-02 22:21
Use Pepin's Tests for proving primality of Mersenne numbers ?	T.Rex	Math	12	2016-04-03 22:27
Proof of Primality Test for Fermat Numbers	princeps	Math	15	2012-04-02 21:49
The fastest primality test for Fermat numbers.	Arkadiusz	Math	6	2011-04-05 19:39
Two Primality tests for Fermat numbers	T.Rex	Math	2	2004-09-11 07:26

2004-02-23, 21:43	#2
dsouza123 Sep 2002 2·331 Posts	Aren't Fermat numbers F5 and above, all composite ?

2004-02-26, 07:49	#4
Cyclamen Persicum Mar 2003 81₁₀ Posts	3^[(Fn-1)/2] = (-1) mod Fn Is this Pepin's test?

2004-05-26, 22:14	#8
ewmayer ∂²ω=0 Sep 2002 República de Califo 2²×2,939 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 LL-style style test on the Fermats, it would be no faster than the Pe'pin test.

2004-05-26, 23:05	#9
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2141₈ 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 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!