20151022, 17:04  #1 
P90 years forever!
Aug 2002
Yeehaw, FL
2^{2}×13×157 Posts 
Alternativelygifted factoring algorithm
I received an email today from someone willing to run this sieving algorithm for f(n)=2n^21:
http://devalco.de/quadr_Sieb_2x%5E21.php to say 2^40 or so. I briefly looked at the algorithm and if I understand it correctly, a list of primes will be generated  some as large as 2^80. We'd then need to test whether those primes divide any Mersenne numbers. Two questions: 1) Is this a worthwhile method of finding factors of Mersenne numbers. 2) Can any improvements be made? 
20151022, 17:53  #2  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:
edit: if we can prove it to find the first n that allows division by another value quickly of the function then we can reduce it to a test of does 2^(q1)/2 mod p = that first n value where q is the exponent in question and we already know how to this test but putting the exponent in binary as on the gimps math page. edit2: (q1)/2 is the exponent we would test in this case though since that's the mod we can test for. Last fiddled with by science_man_88 on 20151022 at 18:38 

20151022, 19:08  #3 
"Forget I exist"
Jul 2009
Dartmouth NS
20342_{8} Posts 
sorry ran out of edit time I just realized that you can turn 2*n^21 into 2*(n^21)+1 assume f(i)=2*i^21 = 2*(i^21)+1 divides by f(n) then we know we can show that which lead to:
which assuming a non zero result suggest to me that: of course a congruence of squares may factorize the number under some factorization methods at last check. 
20151022, 19:22  #4  
"Bob Silverman"
Nov 2003
North of Boston
16524_{8} Posts 
Quote:


20151022, 19:35  #5 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 

20151022, 20:03  #6 
Aug 2002
Buenos Aires, Argentina
3×499 Posts 
It is clear that the method is a lot slower than current method for trial factoring: it does not take advantage of the fact that the prime factors of Mersenne number have the form k*p+1 (it appears that "k" in that Web site has another meaning).
I just see some random numbers that take too long to compute (because lots of divisions have to be done). I would like the author of this method to explain why this method is better than the TF as currently implemented in Prime95. I would also like him to explain why the numbers not generated by that method cannot be factors of Mersenne numbers. 
20151022, 20:46  #7 
If I May
"Chris Halsall"
Sep 2002
Barbados
11,087 Posts 

20151022, 22:25  #8  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
What is the range of f mod 8. And the presentation of the 'algorithm' is a joke. Why take the trouble to insult even a casual reader by presenting the totally trivial fact that if pf(n) then p  f(n+p) as a LEMMA? This is so totally trivial [and also misses a more general case] that no serious author would present it as a 'lemma'. 

20151022, 22:42  #9 
Aug 2002
Buenos Aires, Argentina
3×499 Posts 
It is clear that the prime numbers such that p=3 or p=5 (mod 8) cannot be generated with that choice of f(n), but these primes are already discarded by the current trial factoring code. There is nothing new there.

20151022, 22:46  #10  
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Quote:


20151023, 00:04  #11  
P90 years forever!
Aug 2002
Yeehaw, FL
17744_{8} Posts 
Quote:
When I glanced at the page, I suspected the algorithm would not be efficient. To reply intelligently, I was hoping someone could easily explain why this is an inefficient way to generate factor candidates. It is not obvious to me whether this method generates all 1,7 mod 8 primes (i.e. the method does filter out some candidates) or if the primes it generates early would be more or less likely to divide a Mersenne number (although I don't see why it would be any different than a similarly sized randomly generated 1,7 mod 8 prime). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Shor's Factoring Algorithm  does it even work?  Citrix  Factoring  37  20080816 14:19 
Prime Factoring Algorithm  Visu  Math  66  20080512 13:55 
Faster Factoring Algorithm?  Citrix  Factoring  6  20071223 11:36 
division/remainder algorithm (trial factoring)  TheJudger  Math  4  20071018 19:01 
A new prime factoring algorithm?  Visu  Factoring  22  20061109 10:43 