mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   brent suyama extension in P-1 (https://www.mersenneforum.org/showthread.php?t=8190)

bsquared 2007-05-16 22:11

brent suyama extension in P-1
 
[FONT=Arial][SIZE=2]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 "[FONT=Palatino-Roman~f][SIZE=7][SIZE=2]Optimising the Enhanced [/SIZE][SIZE=2]Standard Continuation of the [/SIZE][SIZE=2]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.[/SIZE][/SIZE][/FONT][/SIZE][/FONT]

[FONT=Arial][SIZE=2]Next, the observations. During the course of implementing brent-suyama, I produced many buggy versions :blush:. 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?[/SIZE][/FONT]

[FONT=Arial][SIZE=2]thanks in advance,[/SIZE][/FONT]
[FONT=Arial][SIZE=2]- ben.[/SIZE][/FONT]

akruppa 2007-05-18 09:51

[QUOTE=bsquared;106274]I attempted to follow the discussion in Kruppa's "Optimising the Enhanced Standard Continuation of the P-1 Factoring Algorithm",
[/QUOTE]

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

Andi47 2007-05-18 12:11

[QUOTE=akruppa;106423]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.
[/QUOTE]

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.

akruppa 2007-05-18 13:09

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

Alex

bsquared 2007-05-18 14:07

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... :whistle:

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

bsquared 2007-05-18 14:10

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?

akruppa 2007-05-18 14:55

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

Alex

R.D. Silverman 2007-05-18 15:41

[QUOTE=akruppa;106459]Yes, [url]ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz[/url]

Alex[/QUOTE]

And (it is) a truly excellent piece of work!

bsquared 2007-05-18 19:12

At the risk of sounding naive, what is a .psl file, and how do I read it? I'm a windows user.

akruppa 2007-05-18 19:24

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


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

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