mersenneforum.org > Math LLT, double-checking and factoring at the same time
 Register FAQ Search Today's Posts Mark Forums Read

 2005-10-12, 18:43 #1 T.Rex     Feb 2004 France 929 Posts 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. So, my question is: 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 : $\large f \ \mid \ 2^q-1$. 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 ....
2005-10-13, 08:31   #2
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

26·181 Posts

Quote:
 Originally Posted by 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.
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

2005-10-13, 10:18   #3
T.Rex

Feb 2004
France

929 Posts

Quote:
 Originally Posted by 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.
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

 2005-10-13, 21:10 #4 T.Rex     Feb 2004 France 929 Posts 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 $L_AT_EX$ paper for this property asap. I'll describe the algorithm later. Tony
2006-02-02, 21:54   #5
T.Rex

Feb 2004
France

929 Posts
Rho Pollard

Quote:
 Originally Posted by 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.
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));
);
}

 2006-02-02, 23:29 #6 Citrix     Jun 2003 2·797 Posts 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.)
2006-02-03, 16:47   #7
T.Rex

Feb 2004
France

929 Posts

Quote:
 Originally Posted by 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.)
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

2006-02-03, 21:25   #8
Numbers

Jun 2005
Near Beetlegeuse

18416 Posts

Quote:
 Originally Posted by T.Rex F(101) and F(101*101) find no factor
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.

2006-02-04, 11:33   #9
T.Rex

Feb 2004
France

929 Posts

Quote:
 Originally Posted by 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 ?
q=67 seems the first prime exponent of a Mersenne composite for which F(q) and F(q*q) find no factor.
Tony

 2006-02-04, 16:49 #10 Numbers     Jun 2005 Near Beetlegeuse 22×97 Posts Thanks Tony. It's not what I wanted to hear, but is at least another tick in the box.
2006-02-08, 06:08   #11
maxal

Feb 2005

22·5·13 Posts

Quote:
 Originally Posted by 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.
First off, I've got slightly different result for F(43) running your program here:
Code:
? F(43)
q: 43 A4188889-28 A4188889-56
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();
}

 Similar Threads Thread Thread Starter Forum Replies Last Post gd_barnes Riesel Prime Search 71 2022-10-02 17:21 Mark Rose GPU to 72 11 2014-08-21 20:25 137ben PrimeNet 6 2012-03-13 04:01 Unregistered Information & Answers 19 2011-07-29 09:57 GP2 Data 10 2003-11-17 14:55

All times are UTC. The time now is 03:24.

Wed Dec 7 03:24:48 UTC 2022 up 111 days, 53 mins, 0 users, load averages: 0.83, 1.09, 1.00