View Single Post
Old 2007-05-16, 22:11   #1
bsquared's Avatar
Feb 2007

2·1,789 Posts
Default brent suyama extension in P-1

I've been implementing various factorization algorithms (as a hobby), and recently got done with a P-1 method which uses the brent-suyama 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 P-1 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 brent-suyama, 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 brent-suyama needs B2 ~= 1100M to find the factor. Any thoughts as to what is happening there? Blind luck?

thanks in advance,
- ben.
bsquared is offline   Reply With Quote