Thread: Links to factoring programs View Single Post
 2008-10-24, 05:04 #5 bsquared     "Ben" 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... Code: 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: 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 2008-10-24 at 05:06 Reason: attempt to fix table formatting