Quote:
Originally Posted by LaurV
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.

FFT is nlogn which is decidedly polynomial. And, the basis of FFT multiplication is polynomial multipoint evaluation (followed by pointwise multiplication)
Quote:
Originally Posted by LaurV
Maybe you found something like this, that could require a polynomial time, but it would require an exponential space.

If you require exponential space, then you need to read/write all those exponential space, and therefore your algo is exponential time.