Topics in Comptuter Algebra: I

Fast integer multiplication and the fast Euclidean algorithm.

Michael Monagan, Department of Mathematics, Simon Fraser University.

Wednesday May 5 and May 12, 2009, K9509, 3:30-5:00pm.

Abstract:
We describe two algorithms for fast integer multiplication.
Both use the discrete Fast Fourier Transform in the integers modulo p.
The first uses three machine primes and Chinese remaindering.
The second is due to Schoenhage.  It is used in the Gnu MultiPrecision integer
arithmetic package.  It uses a large integer modulus, not necessarily prime,
of the form p = 2^(2^k)+1.  To multiply two N digit integers, both algorithms
have complexity O(N log N log log N).

Secondly, we describe Schoenhage's half GCD algorithm (also known as the fast
Euclidean algorithm) for computing the gcd of two two N digit integers.
If either fast integer multplication is used, the complexity of the fast
Euclidean algorithm is O(N log^2 N log log N).