Math software to calculate in different rings.

Question

I was doing computational experiment by using rings of polynomial like this

let $f(x)=x^6+x\in\mathbb{Z_n[x]}$ for any given $n$.

Is there any software which help me to calculate $f(a)$ where $a\in\mathbb{Z_n}$.

Thanks!

Answer 1

Many computer algebra systems are capable of such computation. I mainly deal with GAP (http://www.gap-system.org), where you can do this, for example, in a very simple way like this:

gap> x:=Indeterminate(Rationals,"x");
x
gap> f:=x^6+x;
x^6+x
gap> Value(f,11);
1771572
gap> Value(f,11) mod 19;
12

just to create a polynomial with rational coefficients and then calculate a remainder using mod. Note that here $12$ is in $\mathbb{Z}$, not in $\mathbb{Z_n}$.

On this way, one should know the function PowerModInt( r, e, m ) which returns r^e mod m for integers r, e and m (e non-negative): compare the runtime in the brute-force calculation

gap> 111122^131113345 mod 139; time;
2
33203

which takes about 33 seconds, with the instantly returned result of PowerModInt:

gap> PowerModInt(111122,131113345,139); time;
2
0

This happens because PowerModInt can reduce intermediate results and thus will generally be faster than using r^e mod m, which would compute r^e first and reduce the result afterwards.

A more "algebraically clean" approach could be to create a proper ring $\mathbb{Z_n}$ using Integers mod n, so that both $a$ and $f(a)$ will belong to $\mathbb{Z_n}$, for example:

gap> z42:=Integers mod 42;
(Integers mod 42)
gap> x:=Indeterminate(z42,"x");
x
gap> f:=x^6+x;
x^6+x
gap> a:=Random(z42);
ZmodnZObj( 2, 42 )
gap> Value(f,a);
ZmodnZObj( 24, 42 )

This corresponds to the fact that (2^6+2) mod 42 = 2.

It depends on the circumstances of the experiment whether to use one approach or another, or to use GAP or another system, such as for example PARI/GP (see also this question).

Remark: note the usage of parentheses because of the rules of precedence of mod in GAP: compare

gap> (2^6+2) mod 42;
24

with

gap> 2^6+2 mod 42;
66

because the latter is equivalent to 2^6 + (2 mod 42).