Re: factoring polynomials modulo non-prime

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

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