Mersenne Digest Thursday, May 27 1999 Volume 01 : Number 564
--
Date: Tue, 25 May 1999 22:46:49 EDT
From: [EMAIL PROTECTED]
Subject: Mersenne: Mathematics
I used to feel like a new a decent deal about mathematics until I started
reading this list, and then I found that there were entire paragraphs
(sometimes two) that I could understand. Could anyone recommend some books
that would get my math a little up to speed. I've taken Calc. III in
college, and that's about it. I was planning on grabbing something on
differential equations, but I wondered what else I should study, & maybe
eventually I will know what a FFT is. Thanks.
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
--
Date: Thu, 27 May 1999 11:26:09 GMT
From: "Brian J Beesley" <[EMAIL PROTECTED]>
Subject: Mersenne: Factoring Mersenne numbers
Sorry if this has been mentioned before, but...
I was thinking (always dangerous!) about some of the smaller
Mersenne numbers, like 2^727-1, for which no factors are known.
2^727-1 has 219 digits, and we are pretty darn sure that it has no
prime factors less than 40 digits long. Therefore it would seem
sensible to "assume" that it is the product of only two prime factors.
This may be also a reasonable assumption for some other small
exponents for which no factors are known.
In this case, there exist (large prime) integers a, b such that
(2 * a * n + 1) * (2 * b * n + 1) = 2^n - 1
A bit of rearrangement leads to the equation
2 * a * b * n^2 + (a + b) * n - 2^(n - 1) = 0
which it looks "feasible" to solve - yielding directly the two prime
factors of 2^n-1, assuming the assumption is correct.
On the other hand, if the equation has no integer solutions for a &
b, then we know that the assumption is incorrect, and that there
must therefore be more than two factors of 2^(n-1).
Given that a 219 digit number can't have all that many factors each
bigger than 10^40, it seems that it might be worthwhile trying to
solve the equation, at least for n=727.
Regards
Brian Beesley
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
--
Date: Thu, 27 May 1999 14:48:01 -
From: [EMAIL PROTECTED]
Subject: Re: Mersenne: Factoring Mersenne numbers
Earlier today I wrote:
>
>In this case, there exist (large prime) integers a, b such that
>(2 * a * n + 1) * (2 * b * n + 1) = 2^n - 1
>
>A bit of rearrangement leads to the equation
>
>2 * a * b * n^2 + (a + b) * n - 2^(n - 1) = 0
>
>which it looks "feasible" to solve - yielding directly the two prime
>factors of 2^n-1, assuming the assumption is correct.
Aaargh! The correct rearrangement is
2 * a * b * n^2 + (a + b) * n - (2^(n - 1) - 1) = 0
Doesn't affect the argument, though.
Regards
Brian Beesley
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
--
Date: Thu, 27 May 1999 12:50:28 -0400
From: Jud McCranie <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Factoring Mersenne numbers
At 02:48 PM 5/27/99 +, [EMAIL PROTECTED] wrote:
>>which it looks "feasible" to solve - yielding directly the two prime
>>factors of 2^n-1, assuming the assumption is correct.
>
>Aaargh! The correct rearrangement is
>
>2 * a * b * n^2 + (a + b) * n - (2^(n - 1) - 1) = 0
>
>Doesn't affect the argument, though.
But I don't see how you're going to find a solution of this any faster than
factoring. About 1980 I had an idea similar to this to find a factor that
looked at the remainders of division and did a sort of Newton's method to find
a root, which immediately gave a factor. It worked great when the number was a
square. Otherwise it degenerated into a poor implementation of a brute force
search.
+---+
| Jud McCranie [EMAIL PROTECTED] |
| |
| Inside every composite integer is a prime |
| factor waiting to get out.|
+---+
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
--
Date: Thu, 27 May 1999 23:07:44 -0400 (EDT)
From: lrwiman <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Factoring Mersenne numbers
>I was thinking (always dangerous!) about some of the smaller
>Mersenne numbers, like 2^727-1, for which no factors are known.
>2^727-1 has 219 digits, and we are pretty darn sure that it has no
>prime factors less than 40 digits long. Therefore it would seem
>sensible to "assume" that it is the product of only two prime factors.
>...
>In this case, there exist (large prime) integers a, b such that
>(2 * a * n + 1) *
