 mersenneforum.org Factors in residue of LL test
 Register FAQ Search Today's Posts Mark Forums Read  2003-08-08, 12:40 #1 jocelynl   Sep 2002 2×131 Posts Factors in residue of LL test Can factors be found in the residue of LL test along the way? Could we find one using linear algebra? Tell me what work you have done on this. Joss   2003-08-08, 14:32 #2 cheesehead   "Richard B. Woods" Aug 2002 Wisconsin USA 22·3·641 Posts There's no information in the L-L residue about factors of the Mersenne number on which the L-L test was run. The residue is just the result of ...((((4^2-2)^2-2)^2-2)^2-2)... (mod the Mersenne number)   2003-08-08, 14:50 #3 jocelynl   Sep 2002 10616 Posts I know that! Has anyone done test on these residues? Like GCD, Quadratic test, Linear algebra from the matrix of this residues. Any work you have might help others to find new type of factoring. Joss   2003-08-08, 14:59 #4 cheesehead   "Richard B. Woods" Aug 2002 Wisconsin USA 22·3·641 Posts Then I guess I don't understand your question. I presumed that by "factors" you meant factors of the Mersenne number. The residues are numbers, and one can factor them if one wishes. Which number(s) did you intend to be the subject of factoring? - - - Let's put it another way: S(0) = 4 S(1) = S(0)^2-2 = 14 S(2) = S(1)^2-2 = 194 ... Suppose we were testing 2^123456789-1. What would the fact that S(2) = 194 tell us? Nothing about 2^123456789-1.. The value of every S(n) is exactly the same (before the mod) no matter what the Mersenne number is. The mod operation is not mathematically necessary except for S(p-2), where whether it is congruent to 0 mod 2^p-1 tells us whether 2^p-1 is prime. The only reason for doing mods on the previous S(i) is that if we don't, the S(i) get too large for our computers to store. Doing a mod on a previous S(i) doesn't change the result of the mod on S(p-2). S(123456789) is a constant. It is the same number no matter what Mersenne number the test is working on, before the mod. After the mod, the only thing we know is whether S(123456789) is divisible by the Mersenne number (i.e., whether the remainder = 0) -- if it is, and the Mersenne number is 2^123456791-1, then we've determined that 2^123456791-1 is prime. But we already knew that that is the outcome of the L-L test -- it tells us whether the Mersenne number is prime.   2003-08-08, 15:11 #5 jocelynl   Sep 2002 4068 Posts If you take the s() like one minus the other or any other manipulation and take the GCD there might be a factor in there. Have you done work in that sense. Joss   2003-08-08, 15:23   #6

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts Quote:
 Originally Posted by jocelynl If you take the s() like one minus the other or any other manipulation and take the GCD there might be a factor in there.
Sure. But it won't be a factor of any Mersenne number, except by sheer coincidence -- which you can't know unless you already know factors of the Mersenne number.

Quote:
 Have you done work in that sense.
I've just added some text to my preceding posting, explaining more about why there is no information in the residue about factors of any Mersenne number. If you are talking about factors of some other number, which other number are you talking about?   2003-08-08, 15:36 #7 cheesehead   "Richard B. Woods" Aug 2002 Wisconsin USA 22·3·641 Posts Perhaps the difficulty is that (A) in GIMPS we're so accustomed to the equation S(i) = S(i-1)^2-2 mod (2^p-1) and (B) almost all explanations of the L-L test fail to mention why we do the mods, that (C) we either forget or never realized that all the S(i) are the same (except for the mod, which doesn't change anything about anyone's factors) no matter which Mersenne number we're testing. S(3) = 37634 S(4) = 1416317954 S(5) = 2005956546822746114 S(6) is too big for the dinky calculator I'm using right now to give an exact value, but it's the same value no matter which Mersenne number we're testing -- except if you reduce it by a modulo operation, which (1) doesn't have any bearing on factors of the Mersenne number or any other number and (2) makes no difference in the outcome of the Lucas-Lehner test. S(5) = 2005956546822746114 gives us exactly the same information about the factors of 2^11-1 as it does about factors of (skipping composite exponents just for convenience) 2^13-1 or factors of 2^17-1 or factors of 2^19-1 or factors of 2^23-1 or any other Mersenne number. How can that be? Because the amount of information that S(5) = 2005956546822746114 gives us about the factors of 2^11-1 or of 2^13-1 or of 2^17-1 or of 2^19-1 or of 2^23-1 is ... nothing. Now, S(5) = 2005956546822746114 does give us information about the factors of 2^7-1, but only because of the combination of the facts that 7-2 = 5 and that 2005956546822746114 is evenly divisible by 2^7-1 = 127. The information this gives us, thanks to Lucas and Lehmer, is that 2^7-1's only factors are 1 and itself. But the value of S(5) doesn't give us information about any other Mersenne number.   2003-08-08, 16:02   #8
jocelynl

Sep 2002

2×131 Posts Quote:
 except if you reduce it by a modulo operation, which doesn't have any bearing on factors of the Mersenne number.
The numbers by them self are not in relation with the mersenne number, but there might be a relation if you build a matrix from the mod operation. I will try using linear algebra to find if there is any relation to the the mersenne numbers tested. I'll keep you posted on my work.

Joss   2003-08-08, 16:12   #9

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts Quote:
 Originally Posted by jocelynl The numbers by them self are not in relation with the mersenne number, but there might be a relation if you build a matrix from the mod operation.
Sure, there's a relation between the numbers in the S(i) series -- they're related by the formulas given above. But that relation doesn't tell us anything about factors of any number that we couldn't derive more easily by simpler means.

Quote:
 I will try using linear algebra to find if there is any relation to the the mersenne numbers tested.
You're welcome to entertain yourself. :)   2003-08-08, 16:40 #10 jocelynl   Sep 2002 2·131 Posts At first glance, I was able to find many factors. For Example with M11 s(1)-s(6) doing the gcd(s(1)-s(6),2^11-1)=23 it is also the same with s(2)-s(7), s(3)-s(8 ) and s(4)-s(9). I know that this is a small factor but never the less is contains in the sequence. With the calculator I'm using, I can try it up to 2^4000 so I'll continue testing this area. Joss.   2003-08-08, 17:12   #11
alpertron

Aug 2002
Buenos Aires, Argentina

25148 Posts You've just found Pollard's Rho algorithm

Quote:
 Originally Posted by jocelynl At first glance, I was able to find many factors. For Example with M11 s(1)-s(6) doing the gcd(s(1)-s(6),2^11-1)=23 it is also the same with s(2)-s(7), s(3)-s(8 ) and s(4)-s(9). I know that this is a small factor but never the less is contains in the sequence. With the calculator I'm using, I can try it up to 2^4000 so I'll continue testing this area. Joss.
The method you are using is basically Pollard's Rho algorithm. Please read http://www.csh.rit.edu/~pat/math/quickies/rho/ for an introduction and http://www.frenchfries.net/paul/factoring/theory/pollard.rho.html for code.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post alpertron Miscellaneous Math 17 2012-04-30 15:28 Brain GPU Computing 0 2012-04-12 20:21 JuanTutors Math 3 2004-08-01 19:07 schneelocke PrimeNet 6 2003-11-22 01:26 ixfd64 Math 3 2003-10-16 22:15

All times are UTC. The time now is 14:04.

Wed May 12 14:04:21 UTC 2021 up 34 days, 8:45, 0 users, load averages: 2.60, 2.39, 2.29