20171014, 16:40  #56  
"Andrew Booker"
Mar 2013
5×17 Posts 
Quote:
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 32bit 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. 

20171017, 12:46  #57 
"Andrew Booker"
Mar 2013
5·17 Posts 
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 64bit version also, and I'll think about how best to do that.) 
20171017, 13:06  #58  
"Ben"
Feb 2007
3,371 Posts 
Quote:


20171017, 13:24  #59  
"Andrew Booker"
Mar 2013
85_{10} Posts 
Quote:
Code:
touch makefactortable touch factor.bin 

20171017, 13:49  #60 
"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!

20171017, 14:53  #61  
"Andrew Booker"
Mar 2013
5·17 Posts 
Quote:
I've just added the plain C functions as advertised. (Nothing changes if you're compiling on x86.) It's about 40% slower on 64bit inputs, but only about 15% slower for <= 63 bits. Other than my phone, I no longer have access to a nonx86 machine, though, so I can't do a real test. 

20171019, 16:12  #62  
"Andrew Booker"
Mar 2013
1010101_{2} Posts 
Quote:
Now that we live in a 64bit world, it makes sense to try SQUFOF at larger bit sizes (65126 bits). Is it ever faster than QS in that range, and where is the crossover? 

20171019, 20:04  #63 
"Tilman Neumann"
Jan 2016
Germany
1AC_{16} Posts 
My guess was based on the assumption that the development of PRBrent with Montgomery continued after G&W's publication and that it had a bigger impact than 64bit. That may be wrong.
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 (mpzstyle) 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... 
20171021, 11:02  #64 
"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 stepgiant 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{(p1)(q1)}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)}2r\) 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)^2n\) 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\equiv1\pmod{12}\) then \(p+q\equiv n+1\pmod{24}\), so we can replace k by something involving \(\frac{p+q}{24}\). 
20171031, 19:41  #65 
"Tilman Neumann"
Jan 2016
Germany
2^{2}·107 Posts 

20171031, 21:46  #66 
"Robert Gerbicz"
Oct 2005
Hungary
5·17^{2} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring Mersenne numbers  paulunderwood  Miscellaneous Math  18  20170827 14:56 
Factoring Big Numbers In c#  ShridharRasal  Factoring  10  20080320 17:17 
Question about factoring code  Peter Nelson  Software  9  20050330 18:28 
Factoring Fermat Numbers  Axel Fox  Software  14  20030704 18:57 
Questions about SSE2 code and Factoring  Joe O  Software  2  20020913 23:39 