Work out table of B1/B2 values to factor integers of a given size using factor_pp1 about flint

[kartikv]

Do you want this to be a function of probability, or be fixed? That is, given b and x, one could choose numbers B1 and B2 such that x percent of b-bit numbers are B1-smooth plus at most one factor below B2 (according to the documentation of gmp-ecm, that is what is needed)...is that what you have in mind?

[wbhart]

I don't think this ticket is correct. The pp1 factor method essentially requires p+1 to be B-smooth in order for the number to be able to be factored using this method. The B1 and B2 figures are just the limits in stage 1 and stage 2 that you are prepared to go to looking for B1-smoothness. So it's really just a measure of how much time you want to spend.

You really can't expect a decent proportion of factors of a given size to be found with this method.

Now that we have ECM, there is little point actually running this. It's just like using a single curve from ECM. Admittedly it is faster to run than ECM, so you can get lucky, especially for small numbers.

In summary, I'm not really sure this ticket is worth doing anything with, unless I misunderstood something.

[wbhart]

I suppose we could do the following: Pick a given bitsize. We could generate random integers and trial factor them. If the cofactor has the given bitsize and is not prime, store the original number in an array. Once we have sufficiently many of them, try factoring with n_factor but calling n_factor_pp1 before n_factor_SQUFOF is called. Adjust B1 and the number of calls to n_factor_pp1 until we get the best time for factoring the array of numbers.

I'm not sure whether this will be successful or not. SQUFOF has time complexity conjecturally of O(n^5), which is pretty hard to beat. But we might find we can speed things up from about 53-64 bits or so. On the other hand, ECM would also possibly work in this range, and then you really have a multivariate optimisation problem.

[wbhart]

I did exactly this, and it speeds up factorisation of numbers in the 50-64 bit range that make it this far, by up to a factor of 2.

Anyhow, now fixed in trunk.