Alternatively-gifted factoring algorithm

[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?

[science_man_88]

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.

[science_man_88]

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

[R.D. Silverman]

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???

[science_man_88]

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.

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

[chalsall]

Originally Posted by R.D. Silverman

This is a joke, right???

Yes.

[R.D. Silverman]

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

[alpertron]

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.

[science_man_88]

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 ?

[Prime95]

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