An improved stage 2 to P+-1 factoring algorithms

Alexander Kruppa (INRIA, France)

MSI Computational Mathematics Seminar Series

DATE: 2008-06-12
TIME: 14:00:00 - 15:00:00
LOCATION: John Dedman 1177
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
In this talk I will give a brief introduction to the P-1 and P+1 factoring algorithms and their different "stage 2" variants. One such variant, based on efficient evaluation a polynomial along a geometric progression, is described in more detail along with some recent improvements, which involve factoring the units modulo a highly composite integer into a sum of sets to build the polynomial more quickly, the use of reciprocal Laurent polynomials to speed up the arithmetic and to conserve memory, and application of this stage 2 variant to the P+1 algorithm.
BIO:
http://www.loria.fr/~kruppaal/