Re: factoring polynomials modulo non-prime

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Max Alekseyev [2013-05-01 19:56]:
> On Wed, May 1, 2013 at 11:36 AM, Bill Allombert
> <Bill.Allombert@math.u-bordeaux1.fr> wrote:
> > On Wed, May 01, 2013 at 11:18:34AM -0400, Max Alekseyev wrote:
> >> The first result below is non-sense.
> >> The second one seems to be the way how this situation should be
> >> handled if PARI cannot factor a given polynomial.
> >> Is this a bug?
> >
> > Fundamentally, factoring polynomials over ring which are not domain is not
> > supported.
> 
> I understand. But I believe PARI should produce an error rather than
> incorrect result in this case.

See http://pari.math.u-bordeaux1.fr/faq.html#BIB

``Bugs in this class (Bad Input Bugs, or BIBs for short) are never fixed
whenever a noticeable code complication or performance penalty would occur.''

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:

 ? N = nextprime(10^20);
 ? f = (x^2+1) * Mod(1,N); for (i=1, 10^5, factor(f))
 time = 84 ms.
 ? for (i=1, 10^5, ispseudoprime(N))
 time = 2,181 ms.
 ? for (i=1, 10^5, isprime(N))
 \\ stopped: will need about 21 hours on this machine...

So we definitely can't properly validate user input before calling the function.
It's a design decision to not attempt a partial (= improper) validation
(that's what the "code complication" clause refers to); which would indeed have
caught the problem in your case .


I agree that factor() is badly documented for t_POL inputs, though.
I'll try to improve it :-)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`