mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-05-16, 22:11   #1
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5×653 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
Old 2007-05-18, 09:51   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
akruppa is offline   Reply With Quote
Old 2007-05-18, 12:11   #3
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2·17·73 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
Type the title into google and klick the first link.

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.
Andi47 is offline   Reply With Quote
Old 2007-05-18, 13:09   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

Oh, ok. Looks like I did put it on my page after all, but never linked to it.

Alex
akruppa is offline   Reply With Quote
Old 2007-05-18, 14:07   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5·653 Posts
Default

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...
bsquared is offline   Reply With Quote
Old 2007-05-18, 14:10   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5·653 Posts
Default

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?
bsquared is offline   Reply With Quote
Old 2007-05-18, 14:55   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Yes, ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz

Alex
akruppa is offline   Reply With Quote
Old 2007-05-18, 15:41   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by akruppa View Post
And (it is) a truly excellent piece of work!
R.D. Silverman is offline   Reply With Quote
Old 2007-05-18, 19:12   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5·653 Posts
Default

At the risk of sounding naive, what is a .psl file, and how do I read it? I'm a windows user.
bsquared is offline   Reply With Quote
Old 2007-05-18, 19:24   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Brent tables reservations chris2be8 Factoring 446 2020-04-29 17:08
Extension request LaurV Data 9 2019-04-14 00:13
PCI-E USB 3.0 Extension Cable vsuite GPU Computing 7 2017-07-10 20:45
Curious about the Suyama test siegert81 Math 2 2014-11-23 21:12
Brent-Suyama extension of P-1 factoring S485122 Math 1 2009-08-23 15:21

All times are UTC. The time now is 19:17.

Mon Jul 13 19:17:18 UTC 2020 up 110 days, 16:50, 1 user, load averages: 1.98, 1.81, 1.70

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.