20070516, 22:11  #1 
"Ben"
Feb 2007
2·3·613 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. 
20070518, 09:51  #2  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
Anyway, the bipartite graph stuff isn't needed for the BrentSuyama extension. The point of my thesis was to choose points of evaluation more carefully, but for a usual enhanced standard stage 2, or a polynomial multipoint evaluation (a.k.a. "FFT") stage 2, no graphs are needed to explain anything. The main ideas of the BrentSuyama extension and of pairing are explained in 1.3.4 and 1.3.5 of my thesis. If you have any questions about this explanation, please ask! Also, are you familiar with Montgomery's "Speeding" paper and his PhD thesis? Alex 

20070518, 12:11  #3  
Oct 2004
Austria
2×17×73 Posts 
Quote:
You get the full title by typing Alexander Kruppa into google and klicking the 8th link, so it seems to be quite easy to find. 

20070518, 13:09  #4 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Oh, ok. Looks like I did put it on my page after all, but never linked to it.
Alex 
20070518, 14:07  #5 
"Ben"
Feb 2007
2×3×613 Posts 
Yeah, I found it with google. I also have Montgomery's "Speeding" paper, and it was instrumental in implementing the progression of f(n). In fact, I just looked at it again, and realized that I didn't read far enough! Section 9 in there may have answers to my question, so I'll try to understand that first. After that I'll probably need to take you up on your offer to answer questions...
And by the way, I thought your thesis was very readable  thanks for putting it where google could get to it. As to the observation of my buggy version, I guess that incorrectly implementing the progression of f(x) < f(x+h) may have accidently set up a condition where the highest factor of p1, s, divided g(vw) + g(u) (using montgomery's notation). But this seems to "accidently" happen more often that I thought. I'll shut up now because I'm talking about stuff I don't understand very well yet...  ben Last fiddled with by bsquared on 20070518 at 14:09 Reason: spelling perfectionist... 
20070518, 14:10  #6 
"Ben"
Feb 2007
2·3·613 Posts 
I saw lots of references to Mongomery's PhD thesis, but could not track down a copy. Any suggestions for where I could find it?

20070518, 14:55  #7 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 

20070518, 15:41  #8  
"Bob Silverman"
Nov 2003
North of Boston
7·1,069 Posts 
Quote:


20070518, 19:12  #9 
"Ben"
Feb 2007
E5E_{16} Posts 
At the risk of sounding naive, what is a .psl file, and how do I read it? I'm a windows user.

20070518, 19:24  #10 
"Nancy"
Aug 2002
Alexandria
2467_{10} Posts 
It's really just a .ps file, i.e. PostScript. For *nix systems, there's ghostscript with the assorted plethora of frontends. I think there's Ghostscript for Windows as well. Or maybe there's a PostScript viewer builtin in newer Windows versions, I don't know.
Alex 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Brent tables reservations  chris2be8  Factoring  504  20220718 11:10 
Extension request  LaurV  Data  9  20190414 00:13 
PCIE USB 3.0 Extension Cable  vsuite  GPU Computing  7  20170710 20:45 
Curious about the Suyama test  siegert81  Math  2  20141123 21:12 
BrentSuyama extension of P1 factoring  S485122  Math  1  20090823 15:21 