View Single Post
Old 2008-10-24, 05:04   #5
bsquared's Avatar
Feb 2007

1100110001112 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, p-1, 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 state-of-the-art 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...
digits   msieve-1.38   yafu-1.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:

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 2008-10-24 at 05:06 Reason: attempt to fix table formatting
bsquared is offline   Reply With Quote