Re: FFELT: how to recover the field?

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

* Jeroen Demeyer [2007-12-09 20:00]:
> Bill Allombert wrote:
>> Why are sqrtn(x,p) and x^(1/p) less obvious ?
>
> Karim Belabas wrote:
>> What's wrong with sqrtn(x,p) ?
>
> Okay, true.  I guess I was thinking too much as a programmer instead of
> a mathematician.  By the way, these functions don't work for finite
> field POLMODs, so it's not *that* obvious :-)

The main problem with "finite field POLMODs" is that the construction is
far too general for its own good. Nothing tells us that the modulus is
indeed an irreducible polynomial over the prime field, nor whether 
the prime "field" is not some less convenient finite ring, nor even
whether there is any base ring such that the object makes any sense at
all, e.g. Mod(Pi*x + Mod(1,2), x^2+1) is a valid PARI object...

Have a look at src/basemath/polarit2.c:poltype() to see what I mean
[ the automaton trying to guess a sensible ring for factor() to operate on ]


So we have almost no way of implementing a non-trivial function
operating on these beasts without having to document all kinds of
restrictions which the user must abide by [ he usually won't ], and
which our functions should check [ they usually won't either, leading to
our beloved "Bad Input Bugs" ].

t_FFELTs are intricially restricted so it becomes possible to implement
"standard" algorithms in a relatively simple way.

(t_POLMODs offer very useful generality for *user programming* in GP.
The above comments only state they lead to hopeless complications for
libpari support.)

>> It doesn't seem to be possible currently (only x.p and x.pol work).
>> I'll add x.mod to the allowed member functions
>
> Maybe you could also add lift(x) to make things more analogous to POLMODs.

[ currently, lift() is a copy when t_FFELTs are concerned ]

Good idea, but not trivial to implement. I guess, lift() should act exactly
as x.pol on t_FFELTs. Unfortunately, contrary to t_POLMODs, t_FFELTs mix
badly with t_POLs. (This is a design choice.) For instance

  x * Mod(x,x^2+1) is the same as Mod(x^2, x^2+1) --> Mod(-1, x^2+1)

  x * ffgen(ffinit(3,2)) --> x*x  
  
Although printed in a funny way, x*x is a sensible object, much easier
to operate on than comparable t_POLMODs: t_FFELTs use a variable for
printing purposes only, they ignore variable priorities, and don't make
the t_POLMOD assumption that P(x) * Mod(Q(x), R(x)) is Mod(P*Q,R)

So we have a natural "lift" definition for the coefficients of a t_POL
when the variable of x.mod has (strictly) lower priority than the
polynomial. Otherwise, one can either 

1) scramble the resulting bivariate polynomial (as per the standard
rules of variable priorities and PARI polynomial arithmetic, losing the
original structure), as in 

  ? g = ffgen(ffinit(5,3,x));
  ? lift(g^2 * y^2 + g^2 * y)
  %2 = (y^2 + y)*x^2

This doesn't work well when the variables are the same:

  ? lift(g^2 * x^2 + g^2 * x)
  %3 = x^4 + x^3

2) use '#' variables ( normally involved when printing objects in unknown
variables, e.g. try writebin(file, exotic_var^2 + 1), then read(file)
in a clean session  )

  ? lift(g^2 * y^2 + g^2 * y)
  %2 = #^2*y^2 + #*y

I'm not fond of either solution :-(.

    K.B.
--
Karim Belabas                  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-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`