mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2017-10-14, 16:40   #56
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5×17 Posts
Default

Quote:
Originally Posted by arbooker View Post
I'm experimenting with a 64-bit version using Ben's asm mulredc.
I've got a version of this working now. It's called factor64. Before doing the github thing, I've put the source here in case anyone wants to test it. Both the file download and factor table computation are now embedded in the Makefile (I recommend reading that before building), so the download is under 900MB.

For this version I decided to compress the factor table by storing information only for those numbers coprime to 17#=510510. With that the data file is smaller than before (about 2.5GB) despite the larger pseudoprime and collision tables. Of course that comes with a cost, since there is more overhead needed to use the factor table. I convinced myself that that doesn't matter so much since the extra overhead is needed at most once per prime factor of the number. So the only case where you might notice a difference is in factoring lots of 32-bit numbers, which is fast anyway. I ran a few limited tests, and it seems to run slightly faster than factor63 for numbers below 2^63. Your mileage may vary.
arbooker is offline   Reply With Quote
Old 2017-10-17, 12:46   #57
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5·17 Posts
Default

Quote:
Originally Posted by arbooker View Post
I've got a version of this working now. It's called factor64.
After a few bug fixes and small improvements, I'm ready to release this on github:
https://github.com/arbooker/factor64

This code makes factor63 obsolete, so barring a massive outcry I intend to stop maintaining the latter. (One feature of the old code is a plain C implementation of mulredc, which adds support for other CPUs. It should be possible to write a 64-bit version also, and I'll think about how best to do that.)
arbooker is offline   Reply With Quote
Old 2017-10-17, 13:06   #58
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,371 Posts
Default

Quote:
Originally Posted by arbooker View Post
After a few bug fixes and small improvements, I'm ready to release this on github:
https://github.com/arbooker/factor64
Does anything change about the factor table? I just last night downloaded the file and ran a few tests. Happy to re-run the tests, but hoping to not have to re-download the file.
bsquared is offline   Reply With Quote
Old 2017-10-17, 13:24   #59
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

8510 Posts
Default

Quote:
Originally Posted by bsquared View Post
Does anything change about the factor table? I just last night downloaded the file and ran a few tests. Happy to re-run the tests, but hoping to not have to re-download the file.
No, it's unchanged, so if you run
Code:
touch makefactortable
touch factor.bin
before compiling the latest version, it should be fine.
arbooker is offline   Reply With Quote
Old 2017-10-17, 13:49   #60
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,371 Posts
Default

The new build methodology is much better, IMO. Much smaller file, and makefactortable didn't take long at all to run. factor64 itself is consistently 5% faster or so than factor63, and works great all the way up through 64 bits. Nice work!
bsquared is offline   Reply With Quote
Old 2017-10-17, 14:53   #61
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5·17 Posts
Default

Quote:
Originally Posted by bsquared View Post
The new build methodology is much better, IMO. Much smaller file, and makefactortable didn't take long at all to run. factor64 itself is consistently 5% faster or so than factor63, and works great all the way up through 64 bits. Nice work!
Thanks!

I've just added the plain C functions as advertised. (Nothing changes if you're compiling on x86.) It's about 40% slower on 64-bit inputs, but only about 15% slower for <= 63 bits. Other than my phone, I no longer have access to a non-x86 machine, though, so I can't do a real test.
arbooker is offline   Reply With Quote
Old 2017-10-19, 16:12   #62
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

10101012 Posts
Default

Quote:
Originally Posted by Till View Post
Citing Gower & Wagstaff (http://www.ams.org/journals/mcom/200...-02010-8.pdf):
"On a 32-bit computer, SQUFOF is the clear champion factoring algorithm for numbers between 10^10 and 10^18, and will likely remain so."

I guess it's not the switch to 64-bit architectures that changed that.
Actually, I think that 64-bit does make a big difference. One of the nice features of SQUFOF is that it works with essentially half precision arithmetic. More precisely, when factoring n, most of the arithmetic is performed on numbers at most 2*sqrt(n). On a 32-bit computer, that makes it relatively easy to factor numbers up to 2^62. (I suspect that's why G&W wrote 10^18 instead of 10^19, even though 10^19 < 2^64.) By contrast, Pollard rho needs full precision arithmetic, which would be much slower on a 32-bit computer.

Now that we live in a 64-bit world, it makes sense to try SQUFOF at larger bit sizes (65-126 bits). Is it ever faster than QS in that range, and where is the crossover?
arbooker is offline   Reply With Quote
Old 2017-10-19, 20:04   #63
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

1AC16 Posts
Default

Quote:
Originally Posted by arbooker View Post
Actually, I think that 64-bit does make a big difference.
My guess was based on the assumption that the development of PR-Brent with Montgomery continued after G&W's publication and that it had a bigger impact than 64-bit. That may be wrong.

Quote:
Originally Posted by arbooker View Post
Now that we live in a 64-bit world, it makes sense to try SQUFOF at larger bit sizes (65-126 bits). Is it ever faster than QS in that range, and where is the crossover?
My (Java) PSIQS package has a Squfof implementation that works up to 92 bit or so. It is basically a long implementation with a few (constant complexity) number of big integer (mpz-style) computations. After readjusting my SIQS for smaller inputs, the crossover is at roughly 61 bit. I think Squfof doesn't scale well for more than 64 bits...
Till is offline   Reply With Quote
Old 2017-10-21, 11:02   #64
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5·17 Posts
Default

Here is an idea for improving the worst case performance of Pollard rho.

In the factor64 code, the worst case iteration count on a large semiprime is roughly \(cn^{1/4}\) for some \(c\approx13\). (c is really a slowly growing function of n, but for fixed bit size we can treat it as a constant for all intents and purposes.) This is necessary to find a few stubborn primes with long cycle times.

If we cut rho off at some earlier point (c=3, say) then we will miss some prime factors, but we will know that any surviving n must be a semiprime pq with p and q of comparable size (i.e. both within some estimable factor of \(\sqrt{n}\)). In turn this means that p+q is not too large. Applying baby step-giant step, we can determine the value of p+q (and thus recover p and q, since we also know pq) using \(O(\sqrt{p+q})\) mulmods and hash table lookups. If done optimally I think this should effectively replace c by its square root. I doubt it would have much effect on the average time, but it's hard to say without trying.

Here are a few more details if you're still reading this far. Writing \(k=\frac{p+q}2-\lceil\sqrt{n}\rceil\), we have \(k\ge0\) and \(2^{\frac{(p-1)(q-1)}2}\equiv1\pmod{n}\), so that \(2^{k}\equiv2^{\frac{n+1}2-\lceil\sqrt{n}\rceil}\pmod{n}\). We step through \(k=0,1,2,\ldots\) with Terr's algorithm, i.e. write \(k=\frac{s(s+1)}2-r\) with \(1\le r\le s\), hash the values of \(2^r\pmod{n}\), and look for collisions with \(2^{\frac{s(s+1)}2-\frac{n+1}2+\lceil\sqrt{n}\rceil}\pmod{n}\). Test each collision to see if \((k+\lceil\sqrt{n}\rceil)^2-n\) is a square.

We can save a further constant factor of at least \(\sqrt{12}\) using restrictions on p+q mod powers of 2 and 3, though this makes the coding messier. For instance, if \(n\equiv-1\pmod{12}\) then \(p+q\equiv n+1\pmod{24}\), so we can replace k by something involving \(\frac{p+q}{24}\).
arbooker is offline   Reply With Quote
Old 2017-10-31, 19:41   #65
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

22·107 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
My vintage code outperforms these times (on larger bits), I will give it out.
Still waiting...
Till is offline   Reply With Quote
Old 2017-10-31, 21:46   #66
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5·172 Posts
Default

Quote:
Originally Posted by Till View Post
Still waiting...
Not forgotten, I had another number theory project, but I'm again on the subject (improving the code).
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring Mersenne numbers paulunderwood Miscellaneous Math 18 2017-08-27 14:56
Factoring Big Numbers In c# ShridharRasal Factoring 10 2008-03-20 17:17
Question about factoring code Peter Nelson Software 9 2005-03-30 18:28
Factoring Fermat Numbers Axel Fox Software 14 2003-07-04 18:57
Questions about SSE2 code and Factoring Joe O Software 2 2002-09-13 23:39

All times are UTC. The time now is 12:04.

Sun Mar 7 12:04:10 UTC 2021 up 94 days, 8:15, 0 users, load averages: 1.88, 1.49, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.