En base 10, un número se escribe como una suma de potencias de 10. Así, 307 se escribe 7 x 1 + 0 x 10 + 3 x 102. Del mismo modo, en una base N (que supondremos «grande»), un entero A se escribe
A = a + b × N + c × N2 + ...
donde a, b, c… son números enteros comprendidos entre 0 y N – 1. Para multiplicar dos números de n cifras mediante el algoritmo clásico que se enseña en la escuela primaria, se realizan n2 multiplicaciones de números de una cifra y después unas n sumas (lo que, en la práctica, es «despreciable» frente a las n2 multiplicaciones anteriores). Al utilizar un ordenador, el tiempo de cálculo es, por tanto, proporcional a n2. Si se duplica el número de cifras, el tiempo de cálculo se multiplica por cuatro. Naturalmente, esto solo es «visible» para números de varios miles de cifras.
Sin embargo, este rendimiento puede mejorarse considerablemente mediante la transformada de Fourier, cuya definición se formula en el plano complejo.
-