mersenneforum.org  

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

Reply
 
Thread Tools
Old 2007-06-18, 18:58   #12
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts
Default

Quote:
Originally Posted by ewmayer View Post
No, the book is correct, 22[sup]n[/sup] needs n squarings, but that's just the Fermat number *itself* - for Pepin's test we need to raise some number (typically 3, as it's the smallest eligible candidate) to that power, which needs 2n squarings.
Uh.......

Not to be picky, but I can compute 2^2^n + 1 on any modern computer
without *any* squarings. Of course converting it to decimal takes a bit more
work.............

R.D. Silverman is offline   Reply With Quote
Old 2007-06-18, 19:21   #13
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

23·1,019 Posts
Default

Quote:
Originally Posted by ewmayer View Post
No, the book is correct, 22[sup]n[/sup] needs n squarings, but that's just the Fermat number *itself* - for Pepin's test we need to raise some number (typically 3, as it's the smallest eligible candidate) to that power, which needs 2n squarings.
You just explained why the book is wrong. The book says you need n squarings when in fact you need 2n squarings.
Prime95 is offline   Reply With Quote
Old 2007-06-18, 20:01   #14
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1175510 Posts
Default

Quote:
Originally Posted by Prime95 View Post
You just explained why the book is wrong. The book says you need n squarings when in fact you need 2n squarings.
Ah yes, I was responding to jasong's later quote:

"According to the book 2^2^n+1 requires n squarings..."

and misinterpreted that as meaning "to calculate 2^2^n+1 requires n squarings," which would have been correct, just not relevant to the ensuing primality test of that number.
ewmayer is offline   Reply With Quote
Old 2007-06-18, 20:16   #15
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3·7·167 Posts
Default

I was hoping people would forget my stupid mistake. The book was right, I was wrong.

The mistake I made was that the example given involved F(5), when I thought it involved F(32), F(5) is 2^2^5, so requires 32 squarings.

Sorry for the trouble.

Last fiddled with by jasong on 2007-06-18 at 20:17
jasong is offline   Reply With Quote
Old 2007-06-18, 23:53   #16
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Not to be picky, but I can compute 2^2^n + 1 on any modern computer without *any* squarings. Of course converting it to decimal takes a bit more
work.............
in fact, what does mean "to compute" ?
Is it admissible to store the number in a "sparse" format (e.g., only list indices of nonzero bits) ?
m_f_h is offline   Reply With Quote
Old 2007-06-19, 00:38   #17
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

5×2,351 Posts
Default

Quote:
Originally Posted by m_f_h View Post
Is it admissible to store the number in a "sparse" format (e.g., only list indices of nonzero bits) ?
In effect, that's what we do when we write "Fn".
ewmayer is offline   Reply With Quote
Old 2007-06-19, 12:57   #18
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Lightbulb Records!



Well Jasong if its of any help to you I will give you the results in 2004.

The largest known Fermat prime is F4 = 65537.

The largest known composite Fermat number is F2145351 discovered by J.B. Cosgrave on feb 21, 2003. This number has the factor 3 x 2^2145353 + 1.
It has 645817 digits.

Among others the program by G. Woltman was essential for the discovery.

At the end of May 2003 there was a total of 214 Fermat numbers known to be composite.

Mally
mfgoode is offline   Reply With Quote
Old 2007-06-19, 13:24   #19
m_f_h
 
m_f_h's Avatar
 
Feb 2007

6608 Posts
Default

Quote:
Originally Posted by ewmayer View Post
In effect, that's what we do when we write "Fn".
You oversimplify a bit. I mean, { Fn } is only a very limited subset of Z. What I was suggesting is to code /any/ number, using (maybe conditionally (and maybe recursively)) a sparse format where only indices of nonzero bits are stored.
Just like its commonly done for (sparse) matrices : you can do any operation allowed in the algebra of matrices with them.
Or with polynomials: you may store them as a vector of (all) coefficients, but also as a list of the (nonzero) monomials. When calculating by hand, we usually adopt the latter.
In fact, my idea amounts to that, where any number is seen as a polynomial in 2.
Since this is only a matter of storage (and of efficiently defining the usual operations depending on the storage format), it does not affect the properties of the algebra.

PS: I think your English is getting a bit too much "franglaisé"... ;-)

Last fiddled with by m_f_h on 2007-06-19 at 13:36 Reason: + recursively, + polynomial interpretation
m_f_h is offline   Reply With Quote
Old 2007-06-19, 15:01   #20
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

343410 Posts
Default

Quote:
Originally Posted by mfgoode View Post
At the end of May 2003 there was a total of 214 Fermat numbers known to be composite.

Mally
As of June 2, 2007, 230 Fermat numbers known to be composite:

http://www.prothsearch.net/fermat.html
ATH is offline   Reply With Quote
Old 2007-06-19, 15:53   #21
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

5·2,351 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Not to be picky, but I can compute 2^2^n + 1 on any modern computer without *any* squarings.
I can go one better: one can in fact perform a complete base-2 probable-prime test on any Fn without any computational hardware (other than one's brain, and one doesn't even require much of that) whatsoever.

More generally, one can use the same technique to do a base-2 probable-prime test on any number of form 2n +1 and thereby prove in elementary fashion that such a number can only possibly be prime if n is itself a power of 2.
ewmayer is offline   Reply With Quote
Old 2007-06-19, 22:01   #22
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16458 Posts
Default

Quote:
Originally Posted by ewmayer View Post
As others have noted, direct compositeness test of F33 is currently way out of reach, even on fast multiprocessor hardware. Once we can get the per-iteration time down into the 0.01 second range, we can contemplate such a computation. Perhaps in a decade or so.
Since Pépin's test requires the same time than the LLT, one can use the Mersenne calculator: With a core2 CPU at 3GHz, it would take 3000 years to test F33. I guess that in one decade, using 16 cores instead of one, that would take about 50 years to check F33. Still too long ... If machines with 1024 cores (like Azul machines) are available at that time, then it will take about only 1 year ! 10 years to wait ...
Tony
T.Rex is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ecm with Fermat numbers ET_ FermatSearch 1 2016-08-02 19:40
P-1/P+1 on Fermat numbers ATH Operazione Doppi Mersennes 2 2015-01-25 06:27
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25
Fermat Numbers devarajkandadai Math 8 2004-07-27 12:27
Factoring Fermat Numbers Axel Fox Software 14 2003-07-04 18:57

All times are UTC. The time now is 15:49.


Sun Jan 29 15:49:27 UTC 2023 up 164 days, 13:18, 0 users, load averages: 0.92, 0.98, 0.88

Powered by vBulletin® Version 3.8.11
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.

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