(July 1, 2005)

Magma V2.12-1 (released in July 2005) contains new FFT code for large integer multiplication. This is faster in general than the GMP 4.1.4 large integer FFT multiplication code, as the following tables show.

For each table line, the times are given for multiplying two random integers with the given number of bits in GMP 4.1.4 and Magma V2.12-1. Note that as one increases the bit lengths between powers of two, the timings can jump in non-smooth patterns in both GMP and Magma (because of the nature of the FFT algorithm), but Magma remains faster than GMP for all non-power-of-2 bit lengths tried on the processors listed here.

Multiplication of very large integers has many applications. In particular, one can multiply polynomials over the integers by using the Kronecker-Schoenhage method (also known as segmentation), whereby one evaluates the polynomials at an appropriate power of two B, multiplies the resulting integers, and expands the integer product in base B to obtain the polynomial product.

Magma V2.12-1 not only uses the Kronecker-Schoenhage method when applicable, but also has a direct FFT polynomial multiplication method, which can be even faster (the appropriate method is selected automatically). For example, on an Opteron 150 (2.4GHz) Magma V2.12-1 can multiply two polynomials, each having degree 1000 and 1000-bit integer coefficients, in 0.0125 secs using the direct polynomial FFT method, compared with 0.0307 secs using the Kronecker-Schoenhage method (which involves multiplying two integers close to 2^21 bits each plus the extra overhead of the polynomial expansion and contraction, so is slightly slower than the 2^21-bits Magma timing in the table below).