View Single Post
Old 2011-11-07, 12:20   #6
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22×5×373 Posts

Originally Posted by LaurV View Post
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 (multi-precision).

False. Integer multiplication also takes just polynomial time.

.. 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.
False. FFT multiplication is definitely polynomial.

Three strikes and you are out!

Go back and do some reading. For example,

Go read my joint paper with Peter: An FFT Extension to the P-1 Factoring

Integer multiplication takes polynomial time. The 'paper/pencil'
method is quadratic in the size of the inputs. Integer multiplication via
FFT's takes O(n log n loglogn) where n is the size of the numbers.

The only essential difference between integer and polynomial multiplication is
that for the latter one does not need to handle CARRIES.
R.D. Silverman is offline