Re: Mersenne: Factoring Mersenne
Daniel Grace writes: > Anyway, any mersenne's factor can be written as 2kp+1 > directly). Call (P-1)/p = Q > > Then 2n = Q mod p > n = Q/2 mod p which is well defined > Therefore we can find the sun of the two factors mod p. I think what you are trying to say is M_p is composite for p a prime iff 1+2kp divides (2^(p-1)-1)/p - k for some k>0. If I am not mistaken factoring this using current methods is harder than factoring 2^p - 1. Yup, almost certainly, if only because k is needed twice. The current trial factoring method does not even use k per se. Remeber it is easy to trial divide 2^p - 1 using bit wise operators, because 2^p - 1=1+2+2^2+...+2^(p-1). Let u be a potential divisor (e.g. u=2kp+1) then let j be smallest int. such that 2^j-1>u then you can try dividing 2^p-1 using just j bits of storage. e.g. start with 1+2+2^2+...+2^(j-1), subtract u, shift to the left appending 1's at the start, until you get v>u, subtract u and so on. I think that the software stops if it gets a residue of 0 before all p bits have been eliminated - in this case u divides some smaller Mersenne. Not quite. My "reverse method" works that way, and will find the smallest Mersenne exponent which is a multiple of a given odd number, but the fastest-so-far trial factoring method actually squares and perhaps multiplies by two modulo the trial factor each loop, starting with two and looping over the _bits_ of the Mersenne exponent, making it quite fast. If the particular bit is one, the multiply by two occurs; if it's zero, it doesn't. That is, it calculates the Mersenne number (two to the exponent power) mod the trial factor. This algorithm is in Knuth, apparently, which I don't have a copy of. Before GIMPS, I was doing something slower; George Woltman told me about this method, speeding up my then-current trial factoring program by a factor of about three (in Jan. 1996 or so). Will _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factoring Mersenne
> Anyway, any mersenne's factor can be written as 2kp+1 > > directly). Call (P-1)/p = Q > > Then 2n = Q mod p > n = Q/2 mod p which is well defined > Therefore we can find the sun of the two factors mod p. I think what you are trying to say is M_p is composite for p a prime iff 1+2kp divides (2^(p-1)-1)/p - k for some k>0. If I am not mistaken factoring this using current methods is harder than factoring 2^p - 1. Remeber it is easy to trial divide 2^p - 1 using bit wise operators, because 2^p - 1=1+2+2^2+...+2^(p-1). Let u be a potential divisor (e.g. u=2kp+1) then let j be smallest int. such that 2^j-1>u then you can try dividing 2^p-1 using just j bits of storage. e.g. start with 1+2+2^2+...+2^(j-1), subtract u, shift to the left appending 1's at the start, until you get v>u, subtract u and so on. I think that the software stops if it gets a residue of 0 before all p bits have been eliminated - in this case u divides some smaller Mersenne. Rgds, -- Daniel e-mail: [EMAIL PROTECTED] _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring Mersenne
Hello! I was fiddling around with Mersenne factors the other day and came across an interesting result. I'm not sure if it is of any use, but I think if anyone can extend it just a little further, then it would cut down the numbers we would have to try to factor by a HUGE amount... Anyway, any mersenne's factor can be written as 2kp+1 So any persenne number 2^p - 1 (here on written as P) can be written as (2ap+1)(2bp+1) = P i.f.f. it is not a prime Now define x = p(a+b)+1, y=p(a-b) Then x+y=2ap+1, x-y=2bp+1 so P=(x-y)(x+y) x^2 - y^2 = P Now write n=a+b, m=a-b so x=pn+1 , y=pm Then (pn)^2 + 2pn + 1 + (pm)^2 = P taking this mod p^2 and rearranging a little 2pn = P-1 mod p^2 this means 2pn = (P-1) + pZ for some integer Z so (P-1) must have a factor of p, which we can cancel (we also know this directly). Call (P-1)/p = Q Then 2n = Q mod p n = Q/2 mod p which is well defined Therefore we can find the sun of the two factors mod p. I have tried (and failed so far) to get a similar relationship for y (or a or b) If we could get such a relationship for y, and we assumed we were looking for the smallest factor, then we could work out something about that factor (hopefully it's value mod p) which would cut down on factoring requirements. Any ideas? Chris Jefferson, Girton College, Cambridge, [EMAIL PROTECTED] Someone may have beaten me to Fermat's Last Theorem, but I've done Riemann's general equation. However it won't fit in my signature file... _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
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) * (2 * b * n + 1) = 2^n - 1 Actually, all factors of any 2^n-1 can be expressed in the form 2*a*n+1, including 2^n-1 itself (for prime n, obviously.) -Lucas Wiman Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
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
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
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
