On Tuesday 01 February 2005 10:54, you wrote:

> I'm puzzled.

>

> Symbolic polynomial division (with remainder) can easily be shown to

> be the same level of difficulty as factoring,

As factoring polynomials or integers? As far as I know, factoring polynomials

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.

Décio

[Non-text portions of this message have been removed]