mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2003-08-08, 12:40   #1
jocelynl
 
Sep 2002

2×131 Posts
Default 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
jocelynl is offline   Reply With Quote
Old 2003-08-08, 14:32   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

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)
cheesehead is offline   Reply With Quote
Old 2003-08-08, 14:50   #3
jocelynl
 
Sep 2002

10616 Posts
Default

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
jocelynl is offline   Reply With Quote
Old 2003-08-08, 14:59   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

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.
cheesehead is offline   Reply With Quote
Old 2003-08-08, 15:11   #5
jocelynl
 
Sep 2002

4068 Posts
Default

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
jocelynl is offline   Reply With Quote
Old 2003-08-08, 15:23   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

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?
cheesehead is offline   Reply With Quote
Old 2003-08-08, 15:36   #7
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

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.
cheesehead is offline   Reply With Quote
Old 2003-08-08, 16:02   #8
jocelynl
 
Sep 2002

2×131 Posts
Default

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
jocelynl is offline   Reply With Quote
Old 2003-08-08, 16:12   #9
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

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. :)
cheesehead is offline   Reply With Quote
Old 2003-08-08, 16:40   #10
jocelynl
 
Sep 2002

2·131 Posts
Default

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.
jocelynl is offline   Reply With Quote
Old 2003-08-08, 17:12   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

25148 Posts
Default 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.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Quadratic residue mod 2^p-1 alpertron Miscellaneous Math 17 2012-04-30 15:28
CUDALucas Residue Test (-r) Reference Table Brain GPU Computing 0 2012-04-12 20:21
Can LL residue hit zero before the last iteration? JuanTutors Math 3 2004-08-01 19:07
Masked residue schneelocke PrimeNet 6 2003-11-22 01:26
will searching for factors sometimes be faster than LL test? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.