mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-02-23, 21:10   #1
Erasmus
 
Feb 2004

278 Posts
Default 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)

???
Erasmus is offline   Reply With Quote
Old 2004-02-23, 21:43   #2
dsouza123
 
dsouza123's Avatar
 
Sep 2002

10100101102 Posts
Default

Aren't Fermat numbers F5 and above, all composite ?
dsouza123 is offline   Reply With Quote
Old 2004-02-23, 21:51   #3
nfortino
 
nfortino's Avatar
 
Nov 2003

3·5·11 Posts
Default

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.

Last fiddled with by nfortino on 2004-02-23 at 21:52
nfortino is offline   Reply With Quote
Old 2004-02-26, 07:49   #4
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

5116 Posts
Default

3^[(Fn-1)/2] = (-1) mod Fn
Is this Pepin's test?
Cyclamen Persicum is offline   Reply With Quote
Old 2004-02-26, 12:10   #5
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

34 Posts
Default

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...
Cyclamen Persicum is offline   Reply With Quote
Old 2004-05-24, 14:56   #6
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·3·11·149 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2004-05-26, 21:56   #7
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16228 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2004-05-26, 22:14   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·3·11·149 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2004-05-26, 23:05   #9
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22·32·31 Posts
Default

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!
philmoore is offline   Reply With Quote
Old 2004-05-27, 01:19   #10
Terrence Law
 
May 2004

2×37 Posts
Default 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.
Terrence Law is offline   Reply With Quote
Old 2004-05-27, 02:37   #11
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2·3·293 Posts
Default

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
jinydu is offline   Reply With Quote
Reply

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 79 2020-01-28 08:49
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

All times are UTC. The time now is 20:06.

Sun Nov 29 20:06:26 UTC 2020 up 80 days, 17:17, 4 users, load averages: 1.13, 1.32, 1.27

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