
Calling Sequence


MatGcd(m, A, nrow)


Parameters


m



modulus

A



mod m Matrix; each row stores the coefficients of a polynomial

nrow



number of rows in A containing polynomial coefficients





Description


•

The MatGcd function computes the GCD of the nrow polynomials formed by multiplication of the input Matrix A by the Vector $\[1,x,{x}^{2},...\]$. It is capable of computing the mod m GCD of more than two polynomials simultaneously.

•

Each polynomial must be stored in a row of the input Matrix, in order of increasing degree for the columns. For example, the polynomial ${x}^{2}+2x+3$ is stored in a row as [3, 2, 1].

•

On successful completion, the degree of the GCD is returned, and the coefficients of the GCD are returned in the first row of A.


Note: The returned GCD is not normalized to the leading coefficient 1, as the leading coefficient is required for some modular reconstruction techniques.

•

This command is part of the LinearAlgebra[Modular] package, so it can be used in the form MatGcd(..) only after executing the command with(LinearAlgebra[Modular]). However, it can always be used in the form LinearAlgebra[Modular][MatGcd](..).



Examples


>

with(LinearAlgebra[Modular]):

An example of three polynomials with a known GCD.
>

G := randpoly(x,degree=2,coeffs=rand(0..p1));

${G}{\u2254}{92}{}{{x}}^{{2}}{+}{44}{}{x}{+}{95}$
 (2) 
>

Ac := randpoly(x,degree=2, coeffs=rand(0..p1)): A := expand(G*Ac);

${A}{\u2254}{460}{}{{x}}^{{4}}{+}{5556}{}{{x}}^{{3}}{+}{6983}{}{{x}}^{{2}}{+}{7402}{}{x}{+}{4085}$
 (3) 
>

Bc := randpoly(x,degree=3, coeffs=rand(0..p1)): B := expand(G*Bc);

${B}{\u2254}{3404}{}{{x}}^{{5}}{+}{7884}{}{{x}}^{{4}}{+}{8899}{}{{x}}^{{3}}{+}{16344}{}{{x}}^{{2}}{+}{6650}{}{x}{+}{9025}$
 (4) 
>

Cc := randpoly(x,degree=1, coeffs=rand(0..p1)): C := expand(G*Cc);

${C}{\u2254}{1472}{}{{x}}^{{3}}{+}{8892}{}{{x}}^{{2}}{+}{5436}{}{x}{+}{8455}$
 (5) 
>

cfs := [[seq(coeff(A,x,i),i=0..degree(A,x))],
[seq(coeff(B,x,i),i=0..degree(B,x))],
[seq(coeff(C,x,i),i=0..degree(C,x))]];

${\mathrm{cfs}}{\u2254}\left[\left[{4085}{\,}{7402}{\,}{6983}{\,}{5556}{\,}{460}\right]{\,}\left[{9025}{\,}{6650}{\,}{16344}{\,}{8899}{\,}{7884}{\,}{3404}\right]{\,}\left[{8455}{\,}{5436}{\,}{8892}{\,}{1472}\right]\right]$
 (6) 
>

M := Mod(p,cfs,float[8]);

${M}{\u2254}\left[\begin{array}{cccccc}{11.}& {30.}& {96.}& {27.}& {72.}& {0.}\\ {4.}& {54.}& {48.}& {72.}& {27.}& {9.}\\ {16.}& {4.}& {65.}& {17.}& {0.}& {0.}\end{array}\right]$
 (7) 
$\left[\begin{array}{cccccc}{95.}& {44.}& {92.}& {0.}& {0.}& {0.}\\ {0.}& {0.}& {0.}& {0.}& {0.}& {0.}\\ {0.}& {0.}& {0.}& {0.}& {0.}& {0.}\end{array}\right]{,}{2}$
 (8) 
>

g := add(trunc(M[1,i+1])*x^i,i=0..gdeg);

${g}{\u2254}{92}{}{{x}}^{{2}}{+}{44}{}{x}{+}{95}$
 (9) 
>

modp(Expand(G/lcoeff(G,x)*lcoeff(g,x)),p);

${92}{}{{x}}^{{2}}{+}{44}{}{x}{+}{95}$
 (10) 
An example of a trivial GCD.
>

A := randpoly(x,degree=5);

${A}{\u2254}{62}{}{{x}}^{{5}}{}{82}{}{{x}}^{{4}}{+}{80}{}{{x}}^{{3}}{}{44}{}{{x}}^{{2}}{+}{71}{}{x}{}{17}$
 (11) 
>

B := randpoly(x,degree=4);

${B}{\u2254}{}{75}{}{{x}}^{{4}}{}{10}{}{{x}}^{{3}}{}{7}{}{{x}}^{{2}}{}{40}{}{x}{+}{42}$
 (12) 
>

cfs := [[seq(coeff(A,x,i),i=0..degree(A,x))],
[seq(coeff(B,x,i),i=0..degree(B,x))]]:

>

M := Mod(p,cfs,integer[]);

${M}{\u2254}\left[\begin{array}{cccccc}{80}& {71}& {53}& {80}& {15}& {62}\\ {42}& {57}& {90}& {87}& {22}& {0}\end{array}\right]$
 (13) 
$\left[\begin{array}{cccccc}{75}& {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}\end{array}\right]$
 (15) 


