9
$\begingroup$

Is there a computer algebra system that can do arithmetic over polynomial algebras over finite fields where I can specify the extension?

Exempli gratia, if $f(x), g(x) \in \mathbb{F}_p[\mu]/(m(\mu))[x]$, I'd like the CAS to be able to compute things like $f(x + \mu) + g(x)$ where I specify the polynomial $m(\mu)$.

Thanks

Improve this question
$\endgroup$
3
  • $\begingroup$ Sage has some good stuff, but its a bit obnoxious to use. Still, I suspect you can trick Sage into doing what you want. I would love a decent finite field library myself. $\endgroup$
    – Joseph Victor
    Commented Aug 6, 2012 at 0:28
  • 2
    $\begingroup$ Very large degree polynomials $f$ and $g$? I have something home-made that's primitive in comparison to Sage, but designed for just this sort of thing, yet may choke at huge degree. If you don't get better suggestions, contact me by e-mail. $\endgroup$
    – Lubin
    Commented Aug 6, 2012 at 0:56
  • 1
    $\begingroup$ well, it's not at all hard to do in Sage, see my answer... $\endgroup$
    – Dima Pasechnik
    Commented Aug 7, 2012 at 14:55

6 Answers 6

Reset to default
18
$\begingroup$

You can do these things in Sage quite easily. Here is an example (using Sage 5.2):

sage: Fp.<mu>=GF(5)[]
sage: Fp
Univariate Polynomial Ring in mu over Finite Field of size 5
sage: m=mu^5-mu+1
sage: K.<y>=GF(5^5, name='y', modulus=m) # your mu becomes y
sage: A.<x>=K[]
sage: A
Univariate Polynomial Ring in x over Finite Field in y of size 5^5
sage: f=x^7-1
sage: f(x+y)
x^7 + 2*y*x^6 + y^2*x^5 + (y + 4)*x^2 + (2*y^2 + 3*y)*x + y^3 + 4*y^2 + 4
sage: g=x^2+x+1
sage: f(x+y)+g(x)
x^7 + 2*y*x^6 + y^2*x^5 + y*x^2 + (2*y^2 + 3*y + 1)*x + y^3 + 4*y^2

Another option is to use GAP (kindly provided by A.Konovalov)

gap> R:=PolynomialRing(GF(5),"mu"); mu:=Indeterminate(GF(5));;
GF(5)[mu]
gap> m:=mu^5-mu+1;
mu^5-mu+Z(5)^0
gap> T:=AlgebraicExtension(GF(5),m); a:=RootOfDefiningPolynomial(T);;
<field of size 3125>
gap> A:=PolynomialRing(T,"x"); x:=Indeterminate(T);;
<object>[x]
gap> f:=x^7-1;
x^7-!Z(5)^0
gap> Value(f,x+a);
x^7+Z(5)*a*x^6+a^2*x^5+(a-Z(5)^0)*x^2+(Z(5)*a^2+Z(5)^3*a)*x+(a^3-a^2-Z(5)^0)
gap> g:=x^2+x+One(T); 
x^2+x+!Z(5)^0 
gap> Value(f,x+a)+g; 
x^7+Z(5)*a*x^6+a^2*x^5+a*x^2+(Z(5)*a^2+Z(5)^3*a+Z(5)^0)*x+(a^3-a^2)
Improve this answer
$\endgroup$
6
$\begingroup$

in maxima:

 f(x):= x^3+x+5;
 modulus:5;
 algebraic:true;
 rat(f(u));

returns 2*u+1

Improve this answer
$\endgroup$
2
$\begingroup$

In addition, Magma http://magma.maths.usyd.edu.au/magma/ and GAP http://www.gap-system.org/ will perform these computations. The former is commercial and the latter is free. If you want to compute over large finite fields, then you may want to try Magma.

Stephen Glasby

Improve this answer
$\endgroup$
2
$\begingroup$

Here's one way to do it in Macaulay2

restart
R = GF(5)[mu]/(mu^5-mu+1)[x]
f = x^7-1
g = x^2+x+1
sub(f, x => x+mu) + g

returning

      7        6     2 5       2       2                 3     2
o4 = x  + 2mu*x  + mu x  + mu*x  + (2mu  - 2mu + 1)x + mu  - mu

o4 : R
Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice. I'm not sure if this is better, but as an additional option, it could also be f = x -> x^7-1, and then f(x+mu) and f(x)+g. $\endgroup$
    – Zach Teitler
    Commented Sep 19, 2020 at 5:13
2
$\begingroup$

In Singular:

> ring R = (5,mu),(x),dp; minpoly=mu^5-mu+1;
> poly f = x^7 - 1;
> poly g = x^2 + x + 1;
> subst(f,x,x+mu)+g;
x^7+(2*mu)*x^6+(mu^2)*x^5+(mu)*x^2+(2*mu^2-2*mu+1)*x+(mu^3-mu^2)
Improve this answer
$\endgroup$
0
$\begingroup$

Mathematica has a finite field package which might do what you want.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .