Basic HTML version of Foils prepared May 12 1996

Foil 9 Sieving (RSA-129 and MPQS, RSA-130 and GNFS)

From Lessons and Implementation -- RSA Factoring on the Web CRPC Annual Meeting -- May 14-17 1996. by Geoffrey Fox
RSA129 used the double partial variation of the Multiple Polynomial Quadratic Sieve (MPQS), the predecessor to the Number Field Sieve (NFS), in turn the predecessor to the General Number Field Sieve (GNFS)
General factoring challenge: find x,y such that
  • x^2 == y^2 mod RSA-N.
This would give good odds that
  • gcd(x+y, RSA-N) is not 1 or RSA-N.
Therefore, we'd have a factor of RSA-N.

© Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Sun Dec 14 1997