mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Closed Thread
 
Thread Tools
Old 2015-10-22, 17:04   #1
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2×3×1,193 Posts
Default 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?
Prime95 is offline  
Old 2015-10-22, 17:53   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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
science_man_88 is offline  
Old 2015-10-22, 19:08   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

836910 Posts
Default

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.
science_man_88 is offline  
Old 2015-10-22, 19:22   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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???
R.D. Silverman is offline  
Old 2015-10-22, 19:35   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000101100012 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This is a joke, right???
aren't you usually the one who designates that come back if you have an answer.
science_man_88 is offline  
Old 2015-10-22, 20:03   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

3×5×89 Posts
Default

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.
alpertron is offline  
Old 2015-10-22, 20:46   #7
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

246D16 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This is a joke, right???
Yes.
chalsall is offline  
Old 2015-10-22, 22:25   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by alpertron View Post
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'.
R.D. Silverman is offline  
Old 2015-10-22, 22:42   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

3×5×89 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
alpertron is offline  
Old 2015-10-22, 22:46   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 ?
science_man_88 is offline  
Old 2015-10-23, 00:04   #11
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2·3·1,193 Posts
Default

Quote:
Originally Posted by alpertron View Post
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).
Prime95 is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Shor's Factoring Algorithm - does it even work? Citrix Factoring 37 2008-08-16 14:19
Prime Factoring Algorithm Visu Math 66 2008-05-12 13:55
Faster Factoring Algorithm? Citrix Factoring 6 2007-12-23 11:36
division/remainder algorithm (trial factoring) TheJudger Math 4 2007-10-18 19:01
A new prime factoring algorithm? Visu Factoring 22 2006-11-09 10:43

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

Sat Nov 28 03:07:03 UTC 2020 up 79 days, 18 mins, 3 users, load averages: 1.24, 1.14, 1.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.