Quote:
Originally Posted by LaurV
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,
|
False.
Quote:
|
if the coefficients are huge numbers (multi-precision).
|
False. Integer multiplication also takes just polynomial time.
Quote:
|
.. 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
Algorithm.
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.