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](..).

$\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right)\:$

$p≔97$

$p≔97$

$G≔\mathrm{randpoly}\left(x\,\mathrm{degree}=2\,\mathrm{coeffs}=\mathrm{rand}\left(0..p-1\right)\right)$

$G≔92x^2+44x+95$

$\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≔460x^4+5556x^3+6983x^2+7402x+4085$

$\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≔3404x^5+7884x^4+8899x^3+16344x^2+6650x+9025$

$\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≔1472x^3+8892x^2+5436x+8455$

$\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]$

$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]$

$\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$

$g≔\mathrm{add}\left(\mathrm{trunc}\left(M\left[1,i+1\right]\right)x^i\,i=0..\mathrm{gdeg}\right)$

$g≔92x^2+44x+95$

$\mathrm{modp}\left(\mathrm{Expand}\left(\frac{G}{\mathrm{lcoeff}\left(G\,x\right)}\mathrm{lcoeff}\left(g\,x\right)\right)\,p\right)$

$92x^2+44x+95$

$A≔\mathrm{randpoly}\left(x\,\mathrm{degree}=5\right)$

$A≔62x^5-82x^4+80x^3-44x^2+71x-17$

$B≔\mathrm{randpoly}\left(x\,\mathrm{degree}=4\right)$

$B≔-75x^4-10x^3-7x^2-40x+42$

$\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]$

$\mathrm{MatGcd}\left(p\,M\,2\right)$

$0$

$M$

$\left[\begin{array}{cccccc}75& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$