mersenneforum.org  

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

Reply
 
Thread Tools
Old 2007-06-20, 01:38   #23
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

66638 Posts
Default

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
jasong is offline   Reply With Quote
Old 2007-06-20, 03:14   #24
axn
 
axn's Avatar
 
Jun 2003

153C16 Posts
Default

Quote:
Originally Posted by jasong View Post
F(n) for n=5 to 32 have a known factor
Not quite.
axn is offline   Reply With Quote
Old 2007-06-20, 07:44   #25
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Arrow

Quote:
Originally Posted by ATH View Post
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
mfgoode is offline   Reply With Quote
Old 2007-06-20, 13:53   #26
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DE316 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) ?
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).
jasonp is offline   Reply With Quote
Old 2007-06-20, 17:21   #27
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

5·2,351 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
ewmayer is offline   Reply With Quote
Old 2007-06-20, 18:16   #28
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts
Default

Quote:
Originally Posted by jasonp View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2007-06-20, 18:55   #29
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

thanks for pleading in favour of my idea (indirectly...)
Quote:
Originally Posted by R.D. Silverman View Post
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 ;-) ?
m_f_h is offline   Reply With Quote
Old 2007-06-20, 18:59   #30
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
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
ewmayer is offline   Reply With Quote
Old 2007-06-20, 19:54   #31
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
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-06-20, 20:02   #32
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1175510 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
"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?
ewmayer is offline   Reply With Quote
Old 2007-06-20, 20:32   #33
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
akruppa 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: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.

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