20030808, 12:40  #1 
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 
20030808, 14:32  #2 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
There's no information in the LL residue about factors of the Mersenne number on which the LL test was run.
The residue is just the result of ...((((4^22)^22)^22)^22)... (mod the Mersenne number) 
20030808, 14:50  #3 
Sep 2002
106_{16} 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 
20030808, 14:59  #4 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·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)^22 = 14 S(2) = S(1)^22 = 194 ... Suppose we were testing 2^1234567891. What would the fact that S(2) = 194 tell us? Nothing about 2^1234567891.. 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(p2), where whether it is congruent to 0 mod 2^p1 tells us whether 2^p1 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(p2). 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^1234567911, then we've determined that 2^1234567911 is prime. But we already knew that that is the outcome of the LL test  it tells us whether the Mersenne number is prime. 
20030808, 15:11  #5 
Sep 2002
406_{8} 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 
20030808, 15:23  #6  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Quote:


20030808, 15:36  #7 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Perhaps the difficulty is that (A) in GIMPS we're so accustomed to the equation S(i) = S(i1)^22 mod (2^p1) and (B) almost all explanations of the LL 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 LucasLehner test. S(5) = 2005956546822746114 gives us exactly the same information about the factors of 2^111 as it does about factors of (skipping composite exponents just for convenience) 2^131 or factors of 2^171 or factors of 2^191 or factors of 2^231 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^111 or of 2^131 or of 2^171 or of 2^191 or of 2^231 is ... nothing. Now, S(5) = 2005956546822746114 does give us information about the factors of 2^71, but only because of the combination of the facts that 72 = 5 and that 2005956546822746114 is evenly divisible by 2^71 = 127. The information this gives us, thanks to Lucas and Lehmer, is that 2^71's only factors are 1 and itself. But the value of S(5) doesn't give us information about any other Mersenne number. 
20030808, 16:02  #8  
Sep 2002
2×131 Posts 
Quote:
Joss 

20030808, 16:12  #9  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:
Quote:


20030808, 16:40  #10 
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^111)=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. 
20030808, 17:12  #11  
Aug 2002
Buenos Aires, Argentina
2514_{8} Posts 
You've just found Pollard's Rho algorithm
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Quadratic residue mod 2^p1  alpertron  Miscellaneous Math  17  20120430 15:28 
CUDALucas Residue Test (r) Reference Table  Brain  GPU Computing  0  20120412 20:21 
Can LL residue hit zero before the last iteration?  JuanTutors  Math  3  20040801 19:07 
Masked residue  schneelocke  PrimeNet  6  20031122 01:26 
will searching for factors sometimes be faster than LL test?  ixfd64  Math  3  20031016 22:15 