mersenneforum.org brent suyama extension in P-1
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-16, 22:11 #1 bsquared     "Ben" Feb 2007 22×19×47 Posts 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.
2007-05-18, 09:51   #2
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 Originally Posted by bsquared I attempted to follow the discussion in Kruppa's "Optimising the Enhanced Standard Continuation of the P-1 Factoring Algorithm",
Oh wow... how did you find that? I never put it online anywhere (as far as I remember) because it is not really finished and, frankly, too ugly to read in its current form.

Anyway, the bipartite graph stuff isn't needed for the Brent-Suyama 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 multi-point evaluation (a.k.a. "FFT") stage 2, no graphs are needed to explain anything.

The main ideas of the Brent-Suyama 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

2007-05-18, 12:11   #3
Andi47

Oct 2004
Austria

2·17·73 Posts

Quote:
 Originally Posted by akruppa Oh wow... how did you find that? I never put it online anywhere (as far as I remember) because it is not really finished and, frankly, too ugly to read in its current form.

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.

 2007-05-18, 13:09 #4 akruppa     "Nancy" Aug 2002 Alexandria 246710 Posts Oh, ok. Looks like I did put it on my page after all, but never linked to it. Alex
 2007-05-18, 14:07 #5 bsquared     "Ben" Feb 2007 22×19×47 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 p-1, 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 2007-05-18 at 14:09 Reason: spelling perfectionist...
 2007-05-18, 14:10 #6 bsquared     "Ben" Feb 2007 22·19·47 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?
 2007-05-18, 14:55 #7 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts
2007-05-18, 15:41   #8
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by akruppa
And (it is) a truly excellent piece of work!

 2007-05-18, 19:12 #9 bsquared     "Ben" Feb 2007 357210 Posts At the risk of sounding naive, what is a .psl file, and how do I read it? I'm a windows user.
 2007-05-18, 19:24 #10 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts It's really just a .ps file, i.e. PostScript. For *nix systems, there's ghostscript with the assorted plethora of front-ends. I think there's Ghostscript for Windows as well. Or maybe there's a PostScript viewer built-in in newer Windows versions, I don't know. Alex

 Similar Threads Thread Thread Starter Forum Replies Last Post chris2be8 Factoring 446 2020-04-29 17:08 LaurV Data 9 2019-04-14 00:13 vsuite GPU Computing 7 2017-07-10 20:45 siegert81 Math 2 2014-11-23 21:12 S485122 Math 1 2009-08-23 15:21

All times are UTC. The time now is 06:21.

Wed Sep 22 06:21:01 UTC 2021 up 61 days, 50 mins, 0 users, load averages: 2.52, 1.89, 1.58