MatGcd - Maple Help

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

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right):$
 > $p≔97$
 ${p}{≔}{97}$ (1)

An example of three polynomials with a known GCD.

 > $G≔\mathrm{randpoly}\left(x,\mathrm{degree}=2,\mathrm{coeffs}=\mathrm{rand}\left(0..p-1\right)\right)$
 ${G}{≔}{92}{}{{x}}^{{2}}{+}{44}{}{x}{+}{95}$ (2)
 > $\mathrm{Ac}≔\mathrm{randpoly}\left(x,\mathrm{degree}=2,\mathrm{coeffs}=\mathrm{rand}\left(0..p-1\right)\right):$$A≔\mathrm{expand}\left(G\mathrm{Ac}\right)$
 ${A}{≔}{460}{}{{x}}^{{4}}{+}{5556}{}{{x}}^{{3}}{+}{6983}{}{{x}}^{{2}}{+}{7402}{}{x}{+}{4085}$ (3)
 > $\mathrm{Bc}≔\mathrm{randpoly}\left(x,\mathrm{degree}=3,\mathrm{coeffs}=\mathrm{rand}\left(0..p-1\right)\right):$$B≔\mathrm{expand}\left(G\mathrm{Bc}\right)$
 ${B}{≔}{3404}{}{{x}}^{{5}}{+}{7884}{}{{x}}^{{4}}{+}{8899}{}{{x}}^{{3}}{+}{16344}{}{{x}}^{{2}}{+}{6650}{}{x}{+}{9025}$ (4)
 > $\mathrm{Cc}≔\mathrm{randpoly}\left(x,\mathrm{degree}=1,\mathrm{coeffs}=\mathrm{rand}\left(0..p-1\right)\right):$$C≔\mathrm{expand}\left(G\mathrm{Cc}\right)$
 ${C}{≔}{1472}{}{{x}}^{{3}}{+}{8892}{}{{x}}^{{2}}{+}{5436}{}{x}{+}{8455}$ (5)
 > $\mathrm{cfs}≔\left[\left[\mathrm{seq}\left(\mathrm{coeff}\left(A,x,i\right),i=0..\mathrm{degree}\left(A,x\right)\right)\right],\left[\mathrm{seq}\left(\mathrm{coeff}\left(B,x,i\right),i=0..\mathrm{degree}\left(B,x\right)\right)\right],\left[\mathrm{seq}\left(\mathrm{coeff}\left(C,x,i\right),i=0..\mathrm{degree}\left(C,x\right)\right)\right]\right]$
 ${\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≔\mathrm{Mod}\left(p,\mathrm{cfs},\mathrm{float}\left[8\right]\right)$
 ${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)
 > $\mathrm{gdeg}≔\mathrm{MatGcd}\left(p,M,3\right):$
 > $M,\mathrm{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≔\mathrm{add}\left(\mathrm{trunc}\left(M\left[1,i+1\right]\right){x}^{i},i=0..\mathrm{gdeg}\right)$
 ${g}{≔}{92}{}{{x}}^{{2}}{+}{44}{}{x}{+}{95}$ (9)
 > $\mathrm{modp}\left(\mathrm{Expand}\left(\frac{G}{\mathrm{lcoeff}\left(G,x\right)}\mathrm{lcoeff}\left(g,x\right)\right),p\right)$
 ${92}{}{{x}}^{{2}}{+}{44}{}{x}{+}{95}$ (10)

An example of a trivial GCD.

 > $A≔\mathrm{randpoly}\left(x,\mathrm{degree}=5\right)$
 ${A}{≔}{62}{}{{x}}^{{5}}{-}{82}{}{{x}}^{{4}}{+}{80}{}{{x}}^{{3}}{-}{44}{}{{x}}^{{2}}{+}{71}{}{x}{-}{17}$ (11)
 > $B≔\mathrm{randpoly}\left(x,\mathrm{degree}=4\right)$
 ${B}{≔}{-}{75}{}{{x}}^{{4}}{-}{10}{}{{x}}^{{3}}{-}{7}{}{{x}}^{{2}}{-}{40}{}{x}{+}{42}$ (12)
 > $\mathrm{cfs}≔\left[\left[\mathrm{seq}\left(\mathrm{coeff}\left(A,x,i\right),i=0..\mathrm{degree}\left(A,x\right)\right)\right],\left[\mathrm{seq}\left(\mathrm{coeff}\left(B,x,i\right),i=0..\mathrm{degree}\left(B,x\right)\right)\right]\right]:$
 > $M≔\mathrm{Mod}\left(p,\mathrm{cfs},\mathrm{integer}\left[\right]\right)$
 ${M}{≔}\left[\begin{array}{cccccc}{80}& {71}& {53}& {80}& {15}& {62}\\ {42}& {57}& {90}& {87}& {22}& {0}\end{array}\right]$ (13)
 > $\mathrm{MatGcd}\left(p,M,2\right)$
 ${0}$ (14)
 > $M$
 $\left[\begin{array}{cccccc}{75}& {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}\end{array}\right]$ (15)