help links subscribe changes refresh edit

	FriCAS Library Examples
NoncommutativePolynomials ←	↑	→ Root denesting

PolynomialOverFiniteField

Edit detail for PolynomialOverFiniteField revision 1 of 1

	1
Editor: hemmecke Time: 2014/11/25 07:42:13 GMT+0
Note:

changed:
-
\begin{axiom}
p ==> 3
K ==> PrimeField p
P ==> UnivariatePolynomial('x, K)
x: P := monomial(1,1)$P
f: P := (x+2)*(2*x^5 + x^3 + 2)
g: P := 2*x^3 + x^2 -x +1
f/g
factor f
factor g
k: K := 2
f/k
\end{axiom}

In order to work with a finite field of order $p^n$ where $p$ is a prime, define
the second argument of UnivariatePolynomial as FiniteField(p, n).

\begin{axiom}
F ==> FiniteField(p, 2)
b: Vector F := basis()$F
t: F := b.2
1+t+t^2+t^3
PF ==> UnivariatePolynomial('y, F)
y: PF := monomial(1,1)$PF
pf: PF := (y+2)*(2*y^5 + y^3 + 2)
pg: PF := (2*t+1)*y^3 + (1+t)*y^2 -t*y +1
pf/pg
factor pf
factor pg
\end{axiom}

In case the field property is not needed, IntegerMod would be the way to go.
But note that in general there are zero divisors, so division will not work
(even not in the case where the argument of IntegerMod is a prime).
The reason is IntegerMod doesn't check whether it's argument is prime and so
does not know that it might be an integral domain.

\begin{axiom}
R ==> IntegerMod(p)
PR ==> UnivariatePolynomial('z, R)
z: PR := monomial(1,1)$PR
rf: PR := (z+2)*(2*z^5 + z^3 + 2)
rg: PR := 2*z^3 + z^2 -z +1
rf/rg
F has IntegralDomain
factor rf
factor rg
\end{axiom}

Also note that factorization of rf fails.
The reason most probably is that the used algorithm needs to divide
by some coefficient and it fails to recognize that this is in fact possible
(at least for primes p). In IntegerMod, there simply is no division.

\begin{axiom}
r1: R := 2
r2: R := 1
r1/r2
r2/r1
\end{axiom}

fricas

p ==> 3

Type: Void

fricas

K ==> PrimeField p

Type: Void

fricas

P ==> UnivariatePolynomial('x, K)

Type: Void

fricas

x: P := monomial(1,1)$P

$\label{eq1}x$

(1)

Type: UnivariatePolynomial(x,PrimeField?(3))

fricas

f: P := (x+2)*(2*x^5 + x^3 + 2)

$\label{eq2}{2 \ {{x}^{6}}}+{{x}^{5}}+{{x}^{4}}+{2 \ {{x}^{3}}}+{2 \ x}+ 1$

(2)

Type: UnivariatePolynomial(x,PrimeField?(3))

fricas

g: P := 2*x^3 + x^2 -x +1

$\label{eq3}{2 \ {{x}^{3}}}+{{x}^{2}}+{2 \ x}+ 1$

(3)

Type: UnivariatePolynomial(x,PrimeField?(3))

fricas

f/g

$\label{eq4}{{{x}^{5}}+{2 \ {{x}^{3}}}+ 1}\over{{{x}^{2}}+ 1}$

(4)

Type: Fraction(UnivariatePolynomial(x,PrimeField?(3)))

fricas

factor f

$\label{eq5}2 \ {\left({{x}^{3}}+{{x}^{2}}+ x + 2 \right)}\ {\left({{x}^{2}}+{2 \ x}+ 2 \right)}\ {\left(x + 2 \right)}$

(5)

Type: Factored(UnivariatePolynomial(x,PrimeField?(3)))

fricas

factor g

$\label{eq6}2 \ {\left({{x}^{2}}+ 1 \right)}\ {\left(x + 2 \right)}$

(6)

Type: Factored(UnivariatePolynomial(x,PrimeField?(3)))

fricas

k: K := 2

$\label{eq7}2$

(7)

Type: PrimeField?(3)

fricas

f/k

$\label{eq8}{{x}^{6}}+{2 \ {{x}^{5}}}+{2 \ {{x}^{4}}}+{{x}^{3}}+ x + 2$

(8)

Type: UnivariatePolynomial(x,PrimeField?(3))

In order to work with a finite field of order where is a prime, define the second argument of UnivariatePolynomial as FiniteField?(p, n).

fricas

F ==> FiniteField(p, 2)

Type: Void

fricas

b: Vector F := basis()$F

$\label{eq9}\left[ 1, \: \%A \right]$

(9)

Type: Vector(FiniteField?(3,2))

fricas

t: F := b.2

$\label{eq10}\%A$

(10)

Type: FiniteField?(3,2)

fricas

1+t+t^2+t^3

$\label{eq11}0$

(11)

Type: FiniteField?(3,2)

fricas

PF ==> UnivariatePolynomial('y, F)

Type: Void

fricas

y: PF := monomial(1,1)$PF

$\label{eq12}y$

(12)

Type: UnivariatePolynomial(y,FiniteField?(3,2))

fricas

pf: PF := (y+2)*(2*y^5 + y^3 + 2)

$\label{eq13}{2 \ {{y}^{6}}}+{{y}^{5}}+{{y}^{4}}+{2 \ {{y}^{3}}}+{2 \ y}+ 1$

(13)

Type: UnivariatePolynomial(y,FiniteField?(3,2))

fricas

pg: PF := (2*t+1)*y^3 + (1+t)*y^2 -t*y +1

$\label{eq14}{{\left({2 \ \%A}+ 1 \right)}\ {{y}^{3}}}+{{\left(\%A + 1 \right)}\ {{y}^{2}}}+{2 \ \%A \ y}+ 1$

(14)

Type: UnivariatePolynomial(y,FiniteField?(3,2))

fricas

pf/pg

$\label{eq15}{\left( \begin{array}{@{}l} \displaystyle {{\left(\%A + 1 \right)}\ {{y}^{6}}}+{{\left({2 \ \%A}+ 2 \right)}\ {{y}^{5}}}+{{\left({2 \ \%A}+ 2 \right)}\ {{y}^{4}}}+ \ \ \displaystyle {{\left(\%A + 1 \right)}\ {{y}^{3}}}+{{\left(\%A + 1 \right)}\ y}+{2 \ \%A}+ 2$

(15)

Type: Fraction(UnivariatePolynomial(y,FiniteField?(3,2)))

fricas

factor pf

$\label{eq16}2 \ {\left({{y}^{3}}+{{y}^{2}}+ y + 2 \right)}\ {\left(y + 2 \right)}\ {\left(y + \%A + 1 \right)}\ {\left(y +{2 \ \%A}+ 1 \right)}$

(16)

Type: Factored(UnivariatePolynomial(y,FiniteField?(3,2)))

fricas

factor pg

$\label{eq17}{\left({2 \ \%A}+ 1 \right)}\ {\left({{y}^{2}}+ \%A + 2 \right)}\ {\left(y + \%A \right)}$

(17)

Type: Factored(UnivariatePolynomial(y,FiniteField?(3,2)))

In case the field property is not needed, IntegerMod? would be the way to go. But note that in general there are zero divisors, so division will not work (even not in the case where the argument of IntegerMod? is a prime). The reason is IntegerMod? doesn't check whether it's argument is prime and so does not know that it might be an integral domain.

fricas

R ==> IntegerMod(p)

Type: Void

fricas

PR ==> UnivariatePolynomial('z, R)

Type: Void

fricas

z: PR := monomial(1,1)$PR

$\label{eq18}z$

(18)

Type: UnivariatePolynomial(z,IntegerMod?(3))

fricas

rf: PR := (z+2)*(2*z^5 + z^3 + 2)

$\label{eq19}{2 \ {{z}^{6}}}+{{z}^{5}}+{{z}^{4}}+{2 \ {{z}^{3}}}+{2 \ z}+ 1$

(19)

Type: UnivariatePolynomial(z,IntegerMod?(3))

fricas

rg: PR := 2*z^3 + z^2 -z +1

$\label{eq20}{2 \ {{z}^{3}}}+{{z}^{2}}+{2 \ z}+ 1$

(20)

Type: UnivariatePolynomial(z,IntegerMod?(3))

fricas

rf/rg

   There are 11 exposed and 15 unexposed library operations named / 
      having 2 argument(s) but none was determined to be applicable. 
      Use HyperDoc Browse, or issue
                                )display op /
      to learn more about the available operations. Perhaps 
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named / 
      with argument type(s) 
                    UnivariatePolynomial(z,IntegerMod(3))
                    UnivariatePolynomial(z,IntegerMod(3))

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

Also note that factorization of rf fails. The reason most probably is that the used algorithm needs to divide by some coefficient and it fails to recognize that this is in fact possible (at least for primes p). In IntegerMod?, there simply is no division.

fricas

r1: R := 2

$\label{eq21}2$

(21)

Type: IntegerMod?(3)

fricas

r2: R := 1

$\label{eq22}1$

(22)

Type: IntegerMod?(3)

fricas

r1/r2

   There are 11 exposed and 15 unexposed library operations named / 
      having 2 argument(s) but none was determined to be applicable. 
      Use HyperDoc Browse, or issue
                                )display op /
      to learn more about the available operations. Perhaps 
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named / 
      with argument type(s) 
                                IntegerMod(3)
                                IntegerMod(3)

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.