Quote:
Originally Posted by bsquared
I attempted to follow the discussion in Kruppa's "Optimising the Enhanced Standard Continuation of the P1 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 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