It seems that there are several really fast prime factorization algorithms around (one that looks ideal is quadratic sieving). However, rather than make my own (likely poor) implementation I would like to use a ready-made library for simplicity.
I need to be able to factor integers of up to 15 digits efficiently. Because of that, I'm not looking for the algorithm that necessarily scales asymptotically best since we can assume the numbers being factored are less than 1015.
I've already had a look at some of the implementations listed on Wikipedia's Quadratic Sieve page. However, some of the implementations don't seem well-maintained; some don't have documentation; and so on! I checked if a few well-known libraries, such as Boost, had factorization methods but they don't seem to.
Can anyone recommend a library that fits the above criteria?
Check out MSIEVE library for factoring large integers by Jason Papadopoulos.
Msieve is the result of my efforts to understand and optimize how integers are factored using the most powerful modern algorithms.
This documentation corresponds to version 1.46 of the Msieve library. Do not expect to become a factoring expert just by reading it. I've included a relatively complete list of references that you can and should look up if you want to treat the code as more than a black box to solve your factoring problems.