mersenneforum.org Some code for factoring numbers up to 2^63
 Register FAQ Search Today's Posts Mark Forums Read

2017-10-14, 16:40   #56
arbooker

"Andrew Booker"
Mar 2013

1258 Posts

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.

2017-10-17, 12:46   #57
arbooker

"Andrew Booker"
Mar 2013

5·17 Posts

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

2017-10-17, 13:06   #58
bsquared

"Ben"
Feb 2007

3,371 Posts

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.

2017-10-17, 13:24   #59
arbooker

"Andrew Booker"
Mar 2013

5×17 Posts

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

 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-17, 14:53   #61
arbooker

"Andrew Booker"
Mar 2013

8510 Posts

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.

2017-10-19, 16:12   #62
arbooker

"Andrew Booker"
Mar 2013

5·17 Posts

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?

2017-10-19, 20:04   #63
Till

"Tilman Neumann"
Jan 2016
Germany

22·107 Posts

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

 2017-10-21, 11:02 #64 arbooker     "Andrew Booker" Mar 2013 5516 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}$$.
2017-10-31, 19:41   #65
Till

"Tilman Neumann"
Jan 2016
Germany

22·107 Posts

Quote:
 Originally Posted by R. Gerbicz My vintage code outperforms these times (on larger bits), I will give it out.
Still waiting...

2017-10-31, 21:46   #66
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5×172 Posts

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 paulunderwood Miscellaneous Math 18 2017-08-27 14:56 ShridharRasal Factoring 10 2008-03-20 17:17 Peter Nelson Software 9 2005-03-30 18:28 Axel Fox Software 14 2003-07-04 18:57 Joe O Software 2 2002-09-13 23:39

All times are UTC. The time now is 11:52.

Sun Mar 7 11:52:46 UTC 2021 up 94 days, 8:04, 0 users, load averages: 1.53, 1.55, 1.61