LinearAlgebra[Modular] - Maple Programming Help

Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Modular Subpackage : LinearAlgebra/Modular/MatGcd

LinearAlgebra[Modular]

 MatGcd
 compute mod m GCD from Matrix of coefficients

 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]):
 > p := 97;
 ${p}{≔}{97}$ (1)

An example of three polynomials with a known GCD.

 > G := randpoly(x,degree=2,coeffs=rand(0..p-1));
 ${G}{≔}{92}{}{{x}}^{{2}}{+}{44}{}{x}{+}{95}$ (2)
 > Ac := randpoly(x,degree=2, coeffs=rand(0..p-1)):  A := expand(G*Ac);
 ${A}{≔}{460}{}{{x}}^{{4}}{+}{5556}{}{{x}}^{{3}}{+}{6983}{}{{x}}^{{2}}{+}{7402}{}{x}{+}{4085}$ (3)
 > Bc := randpoly(x,degree=3, coeffs=rand(0..p-1)):  B := expand(G*Bc);
 ${B}{≔}{3404}{}{{x}}^{{5}}{+}{7884}{}{{x}}^{{4}}{+}{8899}{}{{x}}^{{3}}{+}{16344}{}{{x}}^{{2}}{+}{6650}{}{x}{+}{9025}$ (4)
 > Cc := randpoly(x,degree=1, coeffs=rand(0..p-1)):  C := expand(G*Cc);
 ${C}{≔}{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}}{≔}\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}{≔}\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)
 > gdeg := MatGcd(p,M,3):
 > M,gdeg;
 $\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}{≔}{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}{≔}{62}{}{{x}}^{{5}}{-}{82}{}{{x}}^{{4}}{+}{80}{}{{x}}^{{3}}{-}{44}{}{{x}}^{{2}}{+}{71}{}{x}{-}{17}$ (11)
 > B := randpoly(x,degree=4);
 ${B}{≔}{-}{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}{≔}\left[\begin{array}{cccccc}{80}& {71}& {53}& {80}& {15}& {62}\\ {42}& {57}& {90}& {87}& {22}& {0}\end{array}\right]$ (13)
 > MatGcd(p,M,2);
 ${0}$ (14)
 > M;
 $\left[\begin{array}{cccccc}{75}& {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}\end{array}\right]$ (15)