Quote:
Originally Posted by Maximus
Polinomials: C(x)=A(x)*B(x). And it may be used for integer multiplication. FFT does the same.

Ok. Now let's be a little more clear. Multiplying polynomials is always max quadratic in the number of terms. That is, if the polynomials have degree n, then you do maximum about n^2 multiplications. If one polynomial is degree n and one is degree m, then you do maximum (n+1)*(m+1) multiplications. Some algorithms as Karatsuba or else, will do less multiplications. So, multiplying polynomials requires a "polynomial" number of steps. But each step could be exponential inside, if the coefficients are huge numbers (multiprecision)... I would be very surprised if you found an algorithm to multiply polynomials that can be used to multiply integers in polynomial time. I really doubt. Please note that
FFT multiplication is NOT polynomial. Its order is still (sub)exponential.
Maybe you found something like
this, that could require a polynomial time, but it would require an exponential space.
The best algorithm should be the one that make a good compromise between the time and the space.