Register FAQ Search Today's Posts Mark Forums Read

 2015-10-22, 17:04 #1 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 22×13×157 Posts Alternatively-gifted factoring algorithm I received an email today from someone willing to run this sieving algorithm for f(n)=2n^2-1: http://devalco.de/quadr_Sieb_2x%5E2-1.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?
2015-10-22, 17:53   #2
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by Prime95 1) Is this a worthwhile method of finding factors of Mersenne numbers. 2) Can any improvements be made?
I'm not sure about either right now but I can relate this to the reduced LL test since 2*x^2-1 is also the form of A002812

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^(q-1)/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: (q-1)/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 2015-10-22 at 18:38

 2015-10-22, 19:08 #3 science_man_88     "Forget I exist" Jul 2009 Dartmouth NS 203428 Posts sorry ran out of edit time I just realized that you can turn 2*n^2-1 into 2*(n^2-1)+1 assume f(i)=2*i^2-1 = 2*(i^2-1)+1 divides by f(n) then we know we can show that $i^2-1\eq n^2-1 \pmod {2*(n^2-1)+1}$ which lead to: $i^2\eq n^2 \pmod {2*(n^2-1)+1}$ which assuming a non zero result suggest to me that: $i \eq n \pmod {2*(n^2-1)+1}$ of course a congruence of squares may factorize the number under some factorization methods at last check.
2015-10-22, 19:22   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

165248 Posts

Quote:
 Originally Posted by Prime95 I received an email today from someone willing to run this sieving algorithm for f(n)=2n^2-1: http://devalco.de/quadr_Sieb_2x%5E2-1.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?
This is a joke, right???

2015-10-22, 19:35   #5
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 Originally Posted by R.D. Silverman This is a joke, right???
aren't you usually the one who designates that come back if you have an answer.

 2015-10-22, 20:03 #6 alpertron     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.
2015-10-22, 20:46   #7
chalsall
If I May

"Chris Halsall"
Sep 2002

11,087 Posts

Quote:
 Originally Posted by R.D. Silverman This is a joke, right???
Yes.

2015-10-22, 22:25   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

Quote:
 Originally Posted by alpertron 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.
Also, the choice of f(n) = 2n^2-1 is a complete red herring. Ask:
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 p|f(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'.

2015-10-22, 22:42   #9
alpertron

Aug 2002
Buenos Aires, Argentina

3×499 Posts

Quote:
 Originally Posted by R.D. Silverman Also, the choice of f(n) = 2n^2-1 is a complete red herring. Ask: What is the range of f mod 8.
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.

2015-10-22, 22:46   #10
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 Originally Posted by R.D. Silverman Also, the choice of f(n) = 2n^2-1 is a complete red herring. Ask: 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 p|f(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'.
https://oeis.org/A144861 shows a potential author maybe you could email them ?

2015-10-23, 00:04   #11
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

177448 Posts

Quote:
 Originally Posted by alpertron 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.
First off, I believe the email I received did not come from the author of the web page.

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).

 Similar Threads Thread Thread Starter Forum Replies Last Post Citrix Factoring 37 2008-08-16 14:19 Visu Math 66 2008-05-12 13:55 Citrix Factoring 6 2007-12-23 11:36 TheJudger Math 4 2007-10-18 19:01 Visu Factoring 22 2006-11-09 10:43

All times are UTC. The time now is 10:15.

Mon Feb 6 10:15:31 UTC 2023 up 172 days, 7:44, 1 user, load averages: 0.66, 0.97, 1.01