20051012, 18:43  #1 
Feb 2004
France
929 Posts 
LLT, doublechecking 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 q2 steps, as usual ; b) Check the primality in a different way than LLT (x^22) ; c) Sometimes, find (small or medium) factors of composite Mq during LLT, often long time before the step q2. 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^q1 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 : . 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 .... 
20051013, 08:31  #2  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2^{6}·181 Posts 
Quote:
"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 wellknown 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 

20051013, 10:18  #3  
Feb 2004
France
929 Posts 
Quote:
Tony 

20051013, 21:10  #4 
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 paper for this property asap. I'll describe the algorithm later. Tony 
20060202, 21:54  #5  
Feb 2004
France
929 Posts 
Rho Pollard
Quote:
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^q1 finds larger factors of 2^q1, 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^2a (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^22)%M); } LL2(x,M)= { return((((x^22)%M)^22)%M); } F(q)= { print1("q: ",q); M=2^q1; 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(S1S1_,S2S2_); B=gcd(S2S2_,S3S3_); C=gcd(S1S1_,S3S3_); 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)); ); } 

20060202, 23:29  #6 
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.) 
20060203, 16:47  #7  
Feb 2004
France
929 Posts 
Quote:
With prime exponents of Mersenne numbers, it finds mainly small factors. With composite exponents, it maily finds wellknow factors: 2^a1 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^2a, 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^311 or a random number ... So, does someone have an idea if this method helps or not ? Tony 

20060203, 21:25  #8  
Jun 2005
Near Beetlegeuse
184_{16} Posts 
Quote:
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. 

20060204, 11:33  #9  
Feb 2004
France
929 Posts 
Quote:
Tony 

20060204, 16:49  #10 
Jun 2005
Near Beetlegeuse
2^{2}×97 Posts 
Thanks Tony.
It's not what I wanted to hear, but is at least another tick in the box. 
20060208, 06:08  #11  
Feb 2005
2^{2}·5·13 Posts 
Quote:
Code:
? F(43) q: 43 A418888928 A418888956 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^22; { 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(SS_); if(!D,break); A=gcd(D,M); if(A!=1, print1(" ",A,":",i)); ); } { F(q)= local(M); print("q: ",q); M=2^q1; 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(); } 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Double checking  gd_barnes  Riesel Prime Search  71  20221002 17:21 
Double checking, quail factoring, trick question  Mark Rose  GPU to 72  11  20140821 20:25 
What about doublechecking TF/P1?  137ben  PrimeNet  6  20120313 04:01 
Double checking  Unregistered  Information & Answers  19  20110729 09:57 
Graph of leading edge of LL testing (and doublechecking) over time  GP2  Data  10  20031117 14:55 