Msieve documentation

[mak]

How can I view the complete technical documentation Msieve? For example comments and description of techniques implemented in Msieve. I want to make the modification program, but first you need to get acquainted with those that already exist, can our algorithm as it will accelerate the factorization, the existing algorithms. Thank you!

[jasonp]

There is no technical documentation for msieve outside comments in the code. My spare time is so limited that I cannot afford to both write and document.

I'd be happy to answer any questions you may have...

[mak]

Can you describe briefly nested factorization technique? With a further description of the program, I make it out. I'll see with what I can work, and can modify the technique

[jasonp]

If you mean the top-level factorization driver in driver.c, this is intended to deal with any input size by calling the appropriate algorithm, then proceeding recursively on any unfactored numbers once the factorization succeeds. Some algorithms will find small factors no matter how big the input, and others can only split an input into two (possibly composite) factors. So the procedure is therefore:

- run trial division
- run Pollard rho
- put the unfactored part remaining into a factor_list_t structure
- run ECM

for each composite number in the structure {
   test if number is a perfect power (QS and NFS won't work if it is)
   if number is small 
        use SQUFOF or a tiny QS routine
   else
        use the main QS code (and eventually use NFS if the number
        is larger than QS can be expected to handle)

   put any factors found into the factor_list_t; the act of doing
   so will remove all instances of the new factor from all numbers
   currently in the factor_list_t. Also, if GCD(new factor, old factors) > 1
   then remove the common part from the new factor and add it into
   the factor_list_t as well

   if all numbers in the factor_list_t are prime or probable prime, we're done
}

This kind of complexity was very surprising to me, but it's necessary if you want to completely factor any input with no wasted work, finding as many factors at a time as possible. What do you have in mind for improving it?