"Ben"
Feb 2007
2·1,789 Posts

brent suyama extension in P1
I've been implementing various factorization algorithms (as a hobby), and recently got done with a P1 method which uses the brentsuyama extension and crude prime pairing in stage 2. I have a question and a couple observations that I was hoping people more math savvy than I could comment on. First the question. How does using higher powers of x for the functions f(a) and f(b) benefit speed, specifically? I attempted to follow the discussion in Kruppa's "Optimising the Enhanced Standard Continuation of the P1 Factoring Algorithm", Chapter 2, but I don't know much about bipartite graphs and couldn't get very far. Nothing else I could find treats the subject in depth. Is there a simpler conceptual explanation for what's going on there? It seems to say that using, for instance, x^12 allows one to pair more primes and thus you have less modular multiplications, but I can't follow why this works or if there is something else I'm missing.
Next, the observations. During the course of implementing brentsuyama, I produced many buggy versions . What surprised me was that these versions would still occasionally find factors in stage 2, sometimes WAY before they should be found. For instance, in my first try I severely misunderstood the iteration of f(a), and simply computed b^(f(a)) < b^(f(a))*b^(f(d)) rather than using poly eval on arithmatic progressions to compute b^(f(a)) < b^(f(a+d)). But with this clearly wrong version I found the p51 factor of 18^82 + 1 at about B2 = 160M instead of the B2=1100M that is required. The working version of my brentsuyama needs B2 ~= 1100M to find the factor. Any thoughts as to what is happening there? Blind luck?
thanks in advance,
 ben.
