mersenneforum.org > Math What are the Primality Tests ( not factoring! ) for Fermat Numbers?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 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-02-23, 21:43 #2 dsouza123     Sep 2002 2×331 Posts Aren't Fermat numbers F5 and above, all composite ?
2004-02-23, 21:51   #3
nfortino

Nov 2003

3×5×11 Posts

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

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

Mar 2003

34 Posts

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...

2004-05-24, 14:56   #6
ewmayer
2ω=0

Sep 2002
República de California

101101111010112 Posts

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.

 2004-05-26, 21:56 #7 T.Rex     Feb 2004 France 93310 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-26, 22:14 #8 ewmayer ∂2ω=0     Sep 2002 República de California 1175510 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. 25·5·7 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!
 2004-05-27, 01:19 #10 Terrence Law   May 2004 4A16 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 2×3×293 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 ewmayer Computer Science & Computational Number Theory 83 2022-07-01 22:35 T.Rex Math 12 2016-04-03 22:27 princeps Math 15 2012-04-02 21:49 Arkadiusz Math 6 2011-04-05 19:39 T.Rex Math 2 2004-09-11 07:26

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

Wed Feb 8 20:23:27 UTC 2023 up 174 days, 17:52, 1 user, load averages: 1.00, 1.06, 1.00

Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔