Karim Belabas on Mon, 10 Dec 2007 20:15:38 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: FFELT: how to recover the field? |
* 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] `