Some code for factoring numbers up to 2^63 - Page 6

arbooker · 2017-10-14, 16:40

Quote:

Originally Posted by arbooker

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 · 2017-10-17, 12:46

Quote:

Originally Posted by arbooker

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

bsquared · 2017-10-17, 13:06

Quote:

Originally Posted by arbooker

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.

arbooker · 2017-10-17, 13:24

Quote:

Originally Posted by bsquared

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.

bsquared · 2017-10-17, 13:49

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!

arbooker · 2017-10-17, 14:53

Quote:

Originally Posted by bsquared

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 · 2017-10-19, 16:12

Quote:

Originally Posted by Till

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?

Till · 2017-10-19, 20:04

Quote:

Originally Posted by arbooker

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

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

arbooker · 2017-10-21, 11:02

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

Till · 2017-10-31, 19:41

Quote:

Originally Posted by R. Gerbicz

My vintage code outperforms these times (on larger bits), I will give it out.

Still waiting...

R. Gerbicz · 2017-10-31, 21:46

Quote:

Originally Posted by Till

Still waiting...

Not forgotten, I had another number theory project, but I'm again on the subject (improving the code).

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

2017-10-17, 13:49	#60
bsquared "Ben" Feb 2007 3,371 Posts	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!

2017-10-21, 11:02	#64
arbooker "Andrew Booker" Mar 2013 5×17 Posts	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}\).