"Ben"
Feb 2007
110011000111_{2} Posts

I'd like to annouce the availability of a new factorization utility. This is the result of several's years effort to learn more about factorization, arbitrary precision arithmatic, programming, and speed optimizations.
I've implemented siqs, mpqs, qs, ecm, p1, p+1, squfof, rho, and a fast sieve of eratothenes. I've integrated msieve's post processing routines into siqs (from version 1.25, I think, so kinda old but still great for quadratic sieve sized work). It's all structured as a arbitrary precision calculator, like bc or pari/gp.
None of this is helpful for stateoftheart factorization... so I'm calling the library yafu, for Yet Another Factorization Utility. Even so, I hope someone finds it useful. It has a general purpose function, factor, which tries to optimally reduce a number to its factors using a combination of all of the implemented methods. And the siqs implementation, at least on Intel Core2 architectures, is blazingly fast. I've benchmarked it vs. the latest version of msieve (1.38):
timings in seconds...
Code:
digits msieve1.38 yafu1.0 speedup
50 1 0.55 1.818181818
55 2 1.91 1.047120419
60 6 6.17 0.972447326
65 18 17.18 1.047729919
70 45 36.19 1.243437414
75 170 127.69 1.331349362
80 364 268.02 1.358107604
82 1075 710.68 1.512635785
85 1400 901.3 1.553311883
This is on a fast linux workstation. On a windows box I also observed speedups, but not as dramatic. Probably because the compiler I'm using is terrible (MSVC 6.0). On Opterons, it's not quite as good, and I haven't figured out why yet. I haven't bothered to optimize for P4's... they are just too awful at sieving. After 85 digits it starts to lose ground because I haven't started the double large prime variation yet.
I'll make the source code available soon... still cleaning up some stuff.
If you want to check it out, go here to download windows or linux binaries:
http://bbuhrow.googlepages.com/home
I will be continuously adding on and improving things, and suggestions/bug reports are welcome although this should be no implication that I'll promptly add/fix anything :)
happy factoring,
 ben.
Last fiddled with by bsquared on 20081024 at 05:06
Reason: attempt to fix table formatting
