compute mod m GCD from Matrix of coefficients
MatGcd(m, A, nrow)
mod m Matrix; each row stores the coefficients of a polynomial
number of rows in A containing polynomial coefficients
The MatGcd function computes the GCD of the nrow polynomials formed by multiplication of the input Matrix A by the Vector [1,x,x2,...]. 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 x2+2⁢x+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](..).
p ≔ 97
An example of three polynomials with a known GCD.
G ≔ randpoly⁡x,degree=2,coeffs=rand⁡0..p−1
Ac ≔ randpoly⁡x,degree=2,coeffs=rand⁡0..p−1:A ≔ expand⁡G⁢Ac
Bc ≔ randpoly⁡x,degree=3,coeffs=rand⁡0..p−1:B ≔ expand⁡G⁢Bc
Cc ≔ randpoly⁡x,degree=1,coeffs=rand⁡0..p−1:C ≔ expand⁡G⁢Cc
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
M ≔ Mod⁡p,cfs,float8
gdeg ≔ MatGcd⁡p,M,3:
g ≔ add⁡trunc⁡M1,i+1⁢xi,i=0..gdeg
An example of a trivial GCD.
A ≔ randpoly⁡x,degree=5
B ≔ randpoly⁡x,degree=4
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
Download Help Document