> < ^ Date: Sun, 20 Oct 2002 18:16:34 -0500
< ^ From: Avital Oliver <olivera@macs.biu.ac.il >
> < ^ Subject: Re: Polynomials over Z/nZ?

Hello Alon.

I am far from an expert at GAP, but I could suggest the following
workaround. Calculate the multiplication as polynomials over R and 'fix'
them every once in a while my mod'ing all the coeffients by n. I give an
example of the multiplication of (x^2 + 3x) with (-x^3 + 6x^2 - 3) in Z/4Z.
In this example, f is the product of the two polynomials over Z, where
f_fixed is "fixed" by mod'ing the coefficients.

```gap> R := Integers;
Integers
gap> x := Indeterminate(R);
x_1
gap> p := x^2 + 3*x;
3*x_1+x_1^2
gap> q := -x^3 + 6*x^2 - 3;
-3+6*x_1^2-x_1^3
gap> f := p*q;
-9*x_1-3*x_1^2+18*x_1^3+3*x_1^4-x_1^5
gap> f_fixed := UnivariatePolynomial(R,
CoefficientsOfUnivariatePolynomial(f) mod 4);
3*x_1+x_1^2+2*x_1^3+3*x_1^4+3*x_1^5
```

Yours,
Avital.

----- Original Message -----
From: "Alon Amit" <alona@cgen.com>
To: "Multiple recipients of list" <GAP-Forum@dcs.st-and.ac.uk>
Sent: Sunday, October 20, 2002 9:46 PM
Subject: Polynomials over Z/nZ?

Dear Forum,

It seems that GAP is not willing to consider polynomials over the ring
Z/nZ when n is not prime. For instance,

gap> R:=Integers mod 4;
(Integers mod 4)
gap> x:=Indeterminate(R);
Error, You can only create rational functions over a UFD called from

or

gap> PolynomialRing(R);
Error, You can only create rational functions over a UFD called from
(This makes sense, but I'm not _trying_ to create rational functions -
just polynomials...)

As far as I could tell, the manual doesn't indicate that the underlying
ring needs to be a UFD, but all the examples given are over such rings.
Am I missing something? Is there a workaround? I simply need to make
some horrendous polynomial multiplications over Z/4Z.

Thanks,

Alon