mersenneforum.org > Math Are there any Fermat numbers that might be prime?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-06-20, 01:38 #23 jasong     "Jason Goatcher" Mar 2005 66638 Posts Please think of any of the following that are between parentheses as "subscripted." F(0),F(1),F(2),F(3), and F(4) are all prime F(n) for n=5 to 32 have a known factor f(33) is the lowest one which is an unknown Status unknown for F(n) with n-values of 33-35, 40-41,44-47,49-50
2007-06-20, 03:14   #24
axn

Jun 2003

153C16 Posts

Quote:
 Originally Posted by jasong F(n) for n=5 to 32 have a known factor
Not quite.

2007-06-20, 07:44   #25
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

22·33·19 Posts

Quote:
 Originally Posted by ATH As of June 2, 2007, 230 Fermat numbers known to be composite: http://www.prothsearch.net/fermat.html

Thank you ATH for updating my data.

Well these types of records are like grave stones. At least one is added every day and they with time disappear into oblivion !

Lets go in for more lasting things to disagree with!

BTW: I appreciate your trouble and in no way am disagreeing with you

Mally

2007-06-20, 13:53   #26
jasonp
Tribal Bullet

Oct 2004

DE316 Posts

Quote:
 Originally Posted by m_f_h Is it admissible to store the number in a "sparse" format (e.g., only list indices of nonzero bits) ?
The trouble is not representing Fn, it is performing arithmetic modulo Fn. The things you're doing arithmetic on are random bit-strings that have the same number of bits as Fn (it's just like LL tests, Prime95 doesn't bother trying to compress the numbers it works with because it wouldn't do any good).

2007-06-20, 17:21   #27
ewmayer
2ω=0

Sep 2002
República de California

5·2,351 Posts

Quote:
 Originally Posted by jasonp The trouble is not representing Fn, it is performing arithmetic modulo Fn. The things you're doing arithmetic on are random bit-strings that have the same number of bits as Fn
...except in the base-2 PRP case I mentioned above - there, the bitstrings that occur during the repeated square-and-modding are not random. But it's alas not useful for rigorously establishing primality, it only tells you which of the numbers of the general form 2n+1 *could* be prime.

2007-06-20, 18:16   #28
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

Quote:
 Originally Posted by jasonp The trouble is not representing Fn, it is performing arithmetic modulo Fn. The things you're doing arithmetic on are random bit-strings that have the same number of bits as Fn (it's just like LL tests, Prime95 doesn't bother trying to compress the numbers it works with because it wouldn't do any good).
Huh? Computing mod F_n is *easy*. It can be done in linear time (in the
number of bits)

x mod 2^n + 1 --> Put x = A*2^n + B

then x mod 2^n+1 = A*2^n + B + A - A mod 2^n+1 =
A*(2^n+1) + B-A mod 2^n + 1 = B-A mod 2^n + 1

2007-06-20, 18:55   #29
m_f_h

Feb 2007

24·33 Posts

thanks for pleading in favour of my idea (indirectly...)
Quote:
 Originally Posted by R.D. Silverman x mod 2^n + 1 --> Put x = A*2^n + B Then x mod 2^n+1 = A*2^n + B + A - A mod 2^n+1 = A*(2^n+1) + B-A mod 2^n + 1 = B-A mod 2^n + 1
Even easier : A * 2^n + B == A*(-1)+ B (mod 2^n+1).
A less trivial question : what are the nonzero bits of 3^k or 5^k mod Fn?
are they really random ?
if so for 3 and 5, maybe not for some other admissible "seed" (as TRex would certainly call it ;-) ?

2007-06-20, 18:59   #30
ewmayer
2ω=0

Sep 2002
República de California

5×2,351 Posts

Quote:
 Originally Posted by R.D. Silverman Huh? Computing mod F_n is *easy*.
I'm pretty certain Jason P was referring to the *squaring* of a length-F_n random bitstring and/or the accompanying implicit DWT-based mod, not the trivial mod you refer to.

Last fiddled with by ewmayer on 2007-06-20 at 19:00

2007-06-20, 19:54   #31
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

Quote:
 Originally Posted by ewmayer I'm pretty certain Jason P was referring to the *squaring* of a length-F_n random bitstring and/or the accompanying implicit DWT-based mod, not the trivial mod you refer to.
He wrote:

"The trouble is not representing Fn, it is performing arithmetic modulo Fn"

This is pretty clear. He said nothing about squaring a random bitstring.

You are referring to the difficulty of doing a multiplication, A*B. Once
one has the product doing the reduction is easy. The difficulty is getting the
product.

2007-06-20, 20:02   #32
ewmayer
2ω=0

Sep 2002
República de California

1175510 Posts

Quote:
 Originally Posted by R.D. Silverman "The trouble is not representing Fn, it is performing arithmetic modulo Fn"
And in particular, doing multiplication. This is obvious to any one who has done any work with multiprecision arithmetic.

Quote:
 This is pretty clear. He said nothing about squaring a random bitstring.
In the context of testing Fermat numbers for primality, squaring a random bitstring is precisely the kind of arithmetic that dominates the computation. As I'm sure you know very well.

Quote:
 You are referring to the difficulty of doing a multiplication, A*B. Once one has the product doing the reduction is easy. The difficulty is getting the product.
Exactly, and in the present context, it seemed quite clear that this is the crux of the matter. I'm sure you make analogous context-dependent inferences when talking about e.g. NFS all the time. So why do you suddenly need things spelled out in nauseating detail when it comes to a conceptually much simpler algorithm?

2007-06-20, 20:32   #33
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 Originally Posted by R.D. Silverman You are referring to the difficulty of doing a multiplication, A*B. Once one has the product doing the reduction is easy. The difficulty is getting the product.
Of course, nowadays hardly anyone does the full product and then reduces mod Fm any more. There's the DWT for that. Also, to me "performing arithmetic modulo F_n" was quite clearly referring to doing operations in the ring Z/FnZ, which of course includes multiplication. Cutting a bit string in halves and subtracting them may be called reduction mod Fn, but "arithmetic" can be expected to mean more than just the reduction. And beside all that, I think Jason was merely pointing out that even though the modulus may have a simple representation, the values we are actually working with - the residues - usually do not.

Alex

Last fiddled with by akruppa on 2007-06-20 at 20:34

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ FermatSearch 1 2016-08-02 19:40 ATH Operazione Doppi Mersennes 2 2015-01-25 06:27 T.Rex Math 4 2005-05-07 08:25 devarajkandadai Math 8 2004-07-27 12:27 Axel Fox Software 14 2003-07-04 18:57

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

Sun Jan 29 15:37:06 UTC 2023 up 164 days, 13:05, 0 users, load averages: 1.39, 0.93, 0.79

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.

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