Serge D. Mechveliani wrote:
>
> People,
> I have a couple of questions about FiniteFieldExtensionByPolynomial.
> Consider a program like
>
> ------------------------------------------------------- t.spad --
> INT ==> Integer
> PosInt ==> PositiveInteger
> PF ==> PrimeField
> SUP ==> SparseUnivariatePolynomial
> UP ==> UnivariatePolynomial
> FFP ==> FiniteFieldExtensionByPolynomial
>
> )abbrev package FOO Foo
> Foo(p : PosInt, d : SUP(PF p)) : Export == Implementation where
>
> F ==> PF(p)
> eF ==> FFP(F, d)
> Export == with
> g : () -> eF
>
> Implementation == add
> g() : eF == generator() $ eF
> ------------------------------------------------------------------
>
> Here p is prime, F the prime field of p,
> d an irreducible polynomial in F[?],
> eF the extension of F by d
> -- a certain finite field of dimension n = deg d over F.
>
> I need to input elements of eF in some natural way.
> In algebra, eF is, by definition, the field generated over F by the
> roots of d (or -- by any root).
> `Axiom' says that A := generator() $ eF is a certain fixed root of
> d.
> As I recall, it is known that the degrees [A^i i in 0..(n-1)]
> form a linear basis of eF over F.
>
> 1. So, the elements of eF can be parsed as polynomials f : UP(t, F)
> of degree less than n. Namely: parse f : UP(t, F) and substitute
> A for t in f. This produces the element of eF.
>
> (In DoCon, this polynomial representation for eF is open for the user:
> the residue ring F[t]/(d) represented by polynomials).
>
> But this needs computing A^i by new -- while these degrees are
> actually fixed constants belonging to eF.
>
> 2. On the other hand, Axiom exports basis() $ eF
> -- a fixed linear basis of eF over F.
> If I knew that
> basis() = [A^i, i in 0 .. (n-1)] (1),
>
> then I could convert f -> eF without re-computing the degrees of A.
> And this definition of basis() is correct.
>
> 3. Elements of eF can be input as vectors over F by
> represents([a1,...,an]), and this uses basis().
>
> Is there exported any connection between A and this representation
> by basis() ?
>
> If these choices are related as in (1), then the polynomial
> represenation is converted fast to `represents'.
>
Currently (1) holds. And it is likely to remain true in the future.
OTOH computing powers of A in FriCAS is very cheap, so you gain
almost nothing by making extra assumption.
> 4. A minor related question:
> for R : CommutativeRing being inside S : CommutativeRing,
> f : UP(t, R), a : S,
> what is in the Axiom library the simplest way to compute f(a)
> (substitution of a for t in f) ?
>
> Probably, eval(f, t, a) would not work,
> one needs to map f, t, a to a same domain (UP(x, S) ?)
> and then, retract the result ... Is there a simpler way?
There is 'PolynomialCategoryLifting' package. It is debatable
if using it is simpler, but it seems that it provides the only
"canned" way of doing what you want. Note that due to
the way FriCAS type system works you need extra package
for such a function. Also, FriCAS has no notion of R beeing
inside S, you need to provide appropriate injection as
a function.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
