Abstract (Rene Peralta)
We discuss the implementation of the Hypercube variation
of the Multiple Polynomial Quadratic Sieve (HMPQS) integer factorization
algorithm. HMPQS is a variation on Pomerance's Quadratic Sieve algorithm which
inspects many quadratic polynomials looking for quadratic residues
with small prime factors. The polynomials are organized as the nodes
of an $n$-dimensional cube. Since changing polynomials
on the hypercube is cheap, the optimal value
for the size of the sieving interval is much smaller than in other
implementations of the Multiple Polynomial Quadratic Sieve (MPQS).
This makes HMPQS substantially faster than MPQS.
We also describe a relatively fast way to find good parameters for the
single large prime variation of the algorithm. Finally, we report on the
performance of our implementation on factoring several large
numbers for the Cunningham Project.
Last modified: May 4, 1995.
Kim Skak Larsen
(kslarsen@imada.sdu.dk)