LLT, double-checking and factoring at the same time
 

Hi,
While playing with LLT, I've found a quite simple algorithm that both:
a) Run LLT and prove primality of Mersenne numbers in q-2 steps, as usual ;
b) Check the primality in a different way than LLT (x^2-2) ;
c) Sometimes, find (small or medium) factors of composite Mq during LLT, often long time before the step q-2.

Before describing the idea (a mixture of LLT, ideas from Pollard rho, and some extra stuff), I'd like to have your opinion if it is worth or not to continue studying it.

I've written the idea in PARI/gp powered by GMP, and the code has been able to find the following factors in less than 5 hours on a Xeon 2.8 GHz PC.

Looking at the factors found, it appears clealy that many of them are very small and should be found easily by dividing. I have the hope that modifying the algorithm will lead to find more and greater factors. Also, it is possible that using the method with large exponents will lead to factors greatest than 2^68 (trial factoring limit with Prime95).
Nevertheless, some factors are medium size (like 13523129 for q=3529).

Also, since the algorithm finds factors for not all exponents, I have to provide you with the ratio between: "exponents a factor of is found"/"all tested exponents".

I've looked at Cunningham table and did not find information for many of these exponents and I have no idea if my method is faster than other techniques used for 2^q-1 numbers.

[B]So, my question is:[/B]
Though the algorithm finds factors for only a sub part of the candidates, though the factors are quite small, though it costs at least twice the cost of LLT, is it interesting to have an algorithm that: a) does the LLT, b) check primality in another way in //, and c) sometimes find factors ?

Or, is it (again) something already known and inefficient ?


Tony

q f such that : [tex]\large f \ \mid \ 2^q-1[/tex].
1019 2039
1031 2063
1049 33569
1091 87281
1093 43721
1153 267497
1321 7927
1361 8167
1439 46049
1559 3119
1667 13337
1801 28817
1871 14969
1931 3863
2063 4127
2081 266369
2389 267569
2399 5201033
2411 19289
2539 25391
2543 5087
2591 766937
2609 36527
2707 173249
2837 22697
2903 5807
2909 110543
2963 5927
2999 671777
3041 24329
3319 33191
3329 26633
3347 26777
3359 6719
3391 298409
3491 6983
3529 13523129
3701 111031
3767 30137
3779 7559
3793 60689
3851 7703
3863 7727
3907 531353
3917 407369
3923 219689
4289 34313
4391 8783
4447 71153
4507 21381209
4561 72977
4597 73553
4603 626009
4639 194839
4943 9887
4993 79889
5003 10007
5011 80177
5021 40169
5087 40697
5171 10343
5197 31183
5231 41849
5261 42089
5273 38134337
5521 3533441
5639 11279
5717 45737
5743 643217
5791 926561
5843 712847
5861 46889
5939 617657
6131 12263
6197 297457
6199 61991
6323 12647
6367 63671
6397 1944689
6449 51593
6491 12983
6551 13103
6563 13127
6803 217697
6883 1885943
6917 55337
7079 56633
7103 14207
7207 172969
7211 57689
7417 118673
7487 179689
7537 723553
7589 288383
7673 184153
7681 3994121
7883 441449
8101 712889
8111 16223
8269 727673
8377 134033
8513 272417
8663 17327
8741 69929
8867 70937
8951 17903
9127 146033
9137 2704553
9173 495343
9311 1415273
9337 2838449
9341 74729
9343 149489
9397 2405633
9419 18839
9461 75689
9479 18959
9497 531833
9539 19079
9791 19583
9829 14075129
9851 78809
9883 158129
10007 240169
10163 20327
10211 81689
10331 20663
10657 2216657
10663 170609
10691 21383
10753 172049
10799 21599
10861 1477097
11197 268729
....

[QUOTE=T.Rex]Hi,
While playing with LLT, I've found a quite simple algorithm that both:
a) Run LLT and prove primality of Mersenne numbers in q-2 steps, as usual ;
b) Check the primality in a different way than LLT (x^2-2) ;
c) Sometimes, find (small or medium) factors of composite Mq during LLT, often long time before the step q-2.

Before describing the idea (a mixture of LLT, ideas from Pollard rho, and some extra stuff), I'd like to have your opinion if it is worth or not to continue studying it.
[/QUOTE]Without a specification of your algorithm it is rather hard to pass on opinion on its value.

"Ideas from Pollard rho" is a vague description, and not an encouraging one. If you are looking for cycles in the LL residues, for instance, the standard analysis of the rho algorithm will predict that a factor p will be found in O(sqrt p) iterations. Trial division will almost certainly find such factors much more quickly, given that it can be optimized using the well-known conditions on possible prime factors of Mersenne numbers.

I suggest you post a sketch of your algorithm (not a vast amount of source code please, at least not at first) so we can get a better understanding of what you are doing.

Paul

[QUOTE=xilman]If you are looking for cycles in the LL residues, for instance, the standard analysis of the rho algorithm will predict that a factor p will be found in O(sqrt p) iterations. [/QUOTE]If I remember well (no book with me), Pollard also says that f: x --> x^2+c where c=-2 (the LLT function) is not an appropriate function. My previous attempts to use it failed.
Tony

My algorithm is based on a property I had no proof yet.
I've found a proof for this property just now.
I will provide a [tex]L_AT_EX[/tex] paper for this property asap.
I'll describe the algorithm later.
Tony

Rho Pollard
 

[QUOTE=xilman]I suggest you post a sketch of your algorithm (not a vast amount of source code please, at least not at first) so we can get a better understanding of what you are doing.[/QUOTE]Hi Paul,
I've reviewed my code and I've experimented with several options, and I think that the algorithm is 99 % Rho Pollard. So, it does not look very interesting, at first.

However, I've noticed the following:
- the algorithm mainly finds small factors of Mersenne composites,
- often, the algorithm does not find any factor, because they are too large,
- searching for factors of 2^(q*q)-1 instead of 2^q-1 finds larger factors of 2^q-1, for the cost that a factor will be found in much more iterations (something between O(q) and O(q^2) I think ).

As examples (using small exponents for simplicity):
- F(41) finds no factor, though F(41*41) finds 13367 after 3240 iterations.
- F(43) finds only 431 and 9719 after 28 iterations, though F(43*43) finds also 2099863 in 60 iterations.
- F(53) finds only 6361 after 52 iterations, though F(53*53) finds 69431 after 572 iterations.
- F(101) and F(101*101) find no factor.

In the algorithm below (in PARI/gp), using 4, 10 and 2/3 as initial value, or using x^2-a (a different from 2) do not seem to produce very different results.

So, is such a method worth ?

Regards,

Tony


[CODE]
LL(x,M)=
{
return((x^2-2)%M);
}

LL2(x,M)=
{
return((((x^2-2)%M)^2-2)%M);

}

F(q)=
{
print1("q: ",q);

M=2^q-1;

S1_=S1=4;
S2_=S2=10;
S3_=S3=2/3;

for(i=1,2*q,

S1 =LL(S1,M);
S2 =LL(S2,M);
S3 =LL(S3,M);

S1_=LL2(S1_,M);
S2_=LL2(S2_,M);
S3_=LL2(S3_,M);

A=gcd(S1-S1_,S2-S2_);
B=gcd(S2-S2_,S3-S3_);
C=gcd(S1-S1_,S3-S3_);

if(A*B*C==0, break);

if((A!=1)&&(M%A==0), print1(" A",A,"-",i));
if((B!=1)&&(M%B==0), print1(" B",B,"-",i));
if((C!=1)&&(M%C==0), print1(" C",C,"-",i));
);
}
[/CODE]

Does your method produce any pseudoprimes etc or is it a test only for mersenne numbers?


Citrix

(I haven't looked at the code you posted yet.)

[QUOTE=Citrix]Does your method produce any pseudoprimes etc or is it a test only for mersenne numbers?
(I haven't looked at the code you posted yet.)[/QUOTE]The method often finds products of factors of Mersenne composites. I only tested it with Mersenne composites, not other kinds of number, and I don't think it would apply.
With prime exponents of Mersenne numbers, it finds mainly small factors. With composite exponents, it maily finds well-know factors: 2^a-1 of 2^(abc...)-1 .
The idea was to see if running LLT on the 3 different Initial Values was useful to find factors with the Rho Pollard method. In the Rho Pollard method: x^2-a, it has been said that a should be different from 1 and 2. I've experimented with different values and did not see so much differences between 2 and 3, or 2^31-1 or a random number ...
So, does someone have an idea if this method helps or not ?
Tony

[quote=T.Rex]F(101) and F(101*101) find no factor[/quote]
Tony,
For reasons that I hope are not entirely obvious, I find this quite interesting.
Could you please provide more examples of exponents for which it didn't find a factor in either of these two cases, particularly if F(101) is the lowest example of this?

Thank you.

[QUOTE=Numbers]... more examples of exponents for which it didn't find a factor in either of these two cases, particularly if F(101) is the lowest example of this ?
[/QUOTE]q=67 seems the first prime exponent of a Mersenne composite for which F(q) and F(q*q) find no factor.
Tony

Thanks Tony.
It's not what I wanted to hear, but is at least another tick in the box.

[QUOTE=T.Rex]As examples (using small exponents for simplicity):
- F(41) finds no factor, though F(41*41) finds 13367 after 3240 iterations.
- F(43) finds only 431 and 9719 after 28 iterations, though F(43*43) finds also 2099863 in 60 iterations.
- F(53) finds only 6361 after 52 iterations, though F(53*53) finds 69431 after 572 iterations.
- F(101) and F(101*101) find no factor.[/quote]

First off, I've got slightly different result for F(43) running your program here:
[code]? F(43)
q: 43 A4188889-28 A4188889-56[/code]

Regarding the algorithm: I think there is no much sense in computing gcd like A=gcd(S1-S1_,S2-S2_) and then checking if A is a dividor of M. It is no better than computing gcd(S1-S1,M) and gcd(S2-S2_,M) and checking if either is greater than 1. But the latter approach allows to process different starting values independently. And I am not convinced that using several starting values helps much.

The modified program listed below (it uses Pari's Mod type which is more efficient, I believe).

Results are the following:
- F(41): nothing
- F(41*41): 13367 for every starting value
- F(43): 4188889 for starting values 4 and 10, and 431, 2099863 for starting value 2/3
- F(53): 6361 for every starting value
- F(101): nothing

[code]LL(x)= x^2-2;

{ P(q,u) = local(S,S_,D,A,M);
M = component(u,1);
S_=S=u;
for(i=1,2*q,

S = LL(S);
S_ = LL(LL(S_));

D=lift(S-S_);
if(!D,break);
A=gcd(D,M);
if(A!=1, print1(" ",A,":",i));
);
}

{ F(q)= local(M);
print("q: ",q);
M=2^q-1;
print1(A); P(q,Mod(4,M)); print();
print1(B); P(q,Mod(10,M)); print();
print1(C); P(q,Mod(2/3,M)); print();
}[/code]

[QUOTE=maxal]First off, I've got slightly different result for F(43) running your program here:
[code]? F(43)
q: 43 A4188889-28 A4188889-56[/code][/QUOTE] I wrote a program A that displays each factor only once. Then I wrote a simplified version F in order to provide it on the forum. And they seem to differ in some cases, like for 43. So, I've provided result of A(43) instead of F(43). Sorry.
[QUOTE]
Regarding the algorithm: I think there is no much sense in computing gcd like A=gcd(S1-S1_,S2-S2_) and then checking if A is a dividor of M. It is no better than computing gcd(S1-S1_,M) and gcd(S2-S2_,M) and checking if either is greater than 1. But the latter approach allows to process different starting values independently. [/QUOTE]My idea was that mixing values computed from different initial values would lead to more chances to find a factor. Your program shows that the basic Rho Pollard does provide nearly the same factors, but not exactly.[QUOTE]And I am not convinced that using several starting values helps much.[/QUOTE]Your example with 43 shows that 2/3 sometimes provides different factors.

So, do you agree that the conclusion is that this method could find some interesting factors, but with a higher cost than ways already used by prime95 ?
(up to now, I've found NO interesting big factor with this method and Pari ...)
Tony

[QUOTE=T.Rex]My idea was that mixing values computed from different initial values would lead to more chances to find a factor.[/quote]
Mixing values does not help at all. Because of the following trivial observation:
If gcd(S1-S1_,S2-S2_) gives you a factor of M, then the same factor is contained (maybe with others) in both gcd(S1-S1_,M) and gcd(S2-S2_,M).

[QUOTE=T.Rex]Your example with 43 shows that 2/3 sometimes provides different factors.[/quote] Yes, but the amount of work is doubled/tripled/etc. with the number of different starting values.

[QUOTE=T.Rex]So, do you agree that the conclusion is that this method could find some interesting factors, but with a higher cost than ways already used by prime95 ?[/QUOTE]
Maybe.