Arithmetic

• Multiple precision integer arithmetic
• Integer multiplication via classical, Karatsuba and Schönhage-Strassen FFT methods
• Integer division via classical, Karatsuba and Schönhage-Strassen FFT methods
• Greatest common divisor via Weber Accelerated GCD and Schönhage algorithms
• Extended Greatest common divisor via Lehmer and Schönhage algorithms
• Alternative representation of integers in factored form
• Arithmetic functions: Jacobi symbol, Euler $\phi$ function, etc.

Magma includes both the Karatsuba algorithm and the Schönhage-Strassen FFT-based algorithm for the multiplication of integers. The crossover point (where the FFT method beats the Karatsuba method) is currently 2¹⁵ bits (approx. 10000 decimal digits) on Sun SPARC workstations and 2¹⁷ bits (approx. 40000 decimal digits) on Digital Alpha workstations. Assembler macros are used for critical operations and 64-bit operations are used on DEC-Alpha machines. On Sun SPARC workstations, integer multiplication is 25-40% faster than GNU gmp 2.0.2 for integers having up to 10,000 decimal digits. As the size of integers increases beyond this point, the differential between Magma and gmp becomes much greater. In Magma, computing the product of two $10\,000$-bit integers takes 0.0023 seconds on a 400MHz Sun SPARC workstation and 0.0011 seconds on a 333MHz Digital Alpha workstation (a 64-bit machine), respectively. Computing the product of two integers, each having one million decimal digits, takes 3.0 seconds and 2.2 seconds, respectively, on these machines.

Magma also contains an asymptotically-fast integer (and polynomial) division algorithm which reduces division to multiplication with a constant scale factor that is in the practical range. Thus division of integers and polynomials are based on the Karatsuba and Schönhage-Strassen (FFT) methods when applicable. The crossover point for integer division (when the new method outperforms the classical method) is currently at the point of dividing a 2¹² bit (approx. 1200 decimal digit) integer by a 2¹¹ (approx. 600 decimal digit) integer on Sun SPARC workstations.

Finally, Magma contains implementations of the fast classical Lehmer extended GCD (`XGCD') algorithm (which is about 5 times faster than the Euclidean XGCD algorithm) and the Schönhage recursive (``half-GCD'') algorithm, yielding asymptotically-fast GCD and XGCD algorithms. On a Sun SPARC workstation, the crossover point for the Schönhage GCD algorithm (where it beats the classical Accelerated GCD algorithm) is 32768 bits (about 10000 decimal digits), while the crossover point for the Schönhage XGCD algorithm (when it beats the Lehmer XGCD algorithm) is 6000 bits (about 2000 decimal digits). On a 400Mhz Sun SPARC workstation, Magma can compute the GCD of two arbitrary integers, each having a million decimal digits, in 9.0 seconds, and the extended GCD multipliers for the same numbers in 29.9 seconds.