Bill Allombert on Fri, 03 May 2013 23:07:29 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: factoring polynomials modulo non-prime


On Fri, May 03, 2013 at 04:20:44PM -0400, William F Hammond wrote:
> Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> writes in part:
> 
> > . . .
> > For your specific example (modulus = 32), it is easy to detect that the
> > the modulus is composite. But, in general, it is at least as costly to check
> > (let alone prove) primality of N, than it is to factor a polynomial of degree
> > O(1) over the finite field with N elements:
> 
> I'm confused.  The finite field with 32 elements is not the integers
> mod 32.   ???

It is not, but one can still compare the running time.

Cheers,
Bill