Re: ellgroup hangs for certain input on Version 2.6.2 (development git-0f10e3b)

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

* Richard Heylen [2013-11-07 18:22]:
> I know that testing for irreducibiltiy is slow so don't do it. Why
> does ellgroup go into a busy loop? Can't this be detected cheaply and
> the you could have it return some junk quickly?

Not conveniently, the problem is not limited to ellgroup():
  ffgen(reducible polynomial)
returns an invalid object, and any function handling it later may fail
in unpredictable ways. (In practice, with current implementations mostly
infinite loops and wrong results.)

The only convenient place to add a test is in ffgen() itself, to avoid
creating such timebombs in the first place. But, as we agreed, a proper test
would be expensive, so the policy is to put the burden on the user:
restrict to sensible inputs. :-)


Independently: I just committed a patch that implements an alternative
syntax for ffgen. Besides the current ffgen(T),  which allows to use a
well-crafted model Fp[X]/(T) for your finite field Fq, depending on your
application, one can now input directly g = ffgen(q), using only the field
cardinality. And later recover the irreducible polynomial defining the
model as g.mod.

This is less flexible than ffgen(T), but avoids entirely the above
problems: since we generate a model ourselves, we know we can trust it.

N.B. the current implementation of ffinit is very fast in itself, but
provides models that are relatively "slow" for finite field arithmetic.
This may change in the future.

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]
`