> Testing Mersenne primes involves a lot of multiplication (and division) of
> very
> large numbers, but better algorithms are used so that the multiplication time
> is something line O( n^2 log(n) log(log(n)) ).
This is probably a typo: with FFT or similar methods multiplication time
is aproximately O( n log(n) log log(n) ).
BTW, there is a simple method, simple enough to be used by hand,
which already reduces multiplication time to O( n^a ),
where a = log 3 / log 2 = 1.584962501.
In order to multiply two numbers with two digits each,
say M = Ad + B and N = Cd + D, d being the base,
we normally perform four multiplications: AC, AD, BC and BD
in order to get the answer:
MN = AC d^2 + (AD + BC) d + BD
This expression however shows that AD and BC are never used alone:
only the sum matters. This sum can be computed as
AD + BC = (A+B)(C+D) - AC - BD;
notice that AC and BD will be computed anyway
so that now we perform three multiplications instead of four.
We may recursively repeat this process in order to reduce
the number of products from n^2 to n^a;
true, there are many sums, but sums are cheap.
The library gmp (GNU multi-precision) uses this algorithm
although it is much slower than FFT-like methods.
Maybe because it only involves integers,
and there is no danger at all of rounding errors.
I once wrote a gmp-based program to perform LL tests:
for low exponents it worked fine but for the prime 65537
it already took much longer that mprime.
