8. How to get the best of GMP-ECM?

Choice of modular multiplication. The ecm program may choose between 4 kinds

of modular arithmetic:

(1) Montgomery's REDC algorithm at the word level (option -modmuln).

It is quite fast for small numbers, but has quadratic asymptotic

complexity.

(2) classical GMP arithmetic (option -mpzmod).

Has some overhead with respect to (1) for small sizes, but wins

over (1) for larger sizes since it has quasi-linear asymptotic

complexity.

(3) Montgomery's REDC algorithm at high level (option -redc).

This essentially replaces each division by two multiplications.

Slower than (1) and (2) for small inputs, but better for large

or very large inputs.

(4) base-2 arithmetic for numbers dividing 2^n+1 or 2^n-1.

Each division has only linear time, but the multiplication are

more expensive since they are done on larger numbers.