- I'm puzzled.
Symbolic polynomial division (with remainder) can easily be shown to
be the same level of difficulty as factoring, but descriptions of the
algorithm such as that shown at
http://mathworld.wolfram.com/LongDivision.html appear to be of about
the same level of difficulty as multiplication!? Obviously it can't
Where am I going wrong?
- On Tuesday 01 February 2005 10:54, you wrote:
> I'm puzzled.As factoring polynomials or integers? As far as I know, factoring polynomials
> Symbolic polynomial division (with remainder) can easily be shown to
> be the same level of difficulty as factoring,
is polynomial-time. At least factoring in Z/pZ.
By the way, this underscores the main problem: what is the underlying field
that you're doing factoring on? The relative complexity for each operation
may be different depending on the field.
[Non-text portions of this message have been removed]