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
G ≔ 92⁢x2+44⁢x+95
Ac ≔ randpoly⁡x,degree=2,coeffs=rand⁡0..p−1:A ≔ expand⁡G⁢Ac
A ≔ 460⁢x4+5556⁢x3+6983⁢x2+7402⁢x+4085
Bc ≔ randpoly⁡x,degree=3,coeffs=rand⁡0..p−1:B ≔ expand⁡G⁢Bc
B ≔ 3404⁢x5+7884⁢x4+8899⁢x3+16344⁢x2+6650⁢x+9025
Cc ≔ randpoly⁡x,degree=1,coeffs=rand⁡0..p−1:C ≔ expand⁡G⁢Cc
C ≔ 1472⁢x3+8892⁢x2+5436⁢x+8455
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
cfs ≔ 4085,7402,6983,5556,460,9025,6650,16344,8899,7884,3404,8455,5436,8892,1472
M ≔ Mod⁡p,cfs,float
M ≔ 22.214.171.124.126.96.36.199.188.8.131.52.184.108.40.206.0.0.
gdeg ≔ MatGcd⁡p,M,3:
g ≔ add⁡trunc⁡M1,i+1⁢xi,i=0..gdeg
g ≔ 92⁢x2+44⁢x+95
An example of a trivial GCD.
A ≔ randpoly⁡x,degree=5
A ≔ 62⁢x5−82⁢x4+80⁢x3−44⁢x2+71⁢x−17
B ≔ randpoly⁡x,degree=4
B ≔ −75⁢x4−10⁢x3−7⁢x2−40⁢x+42
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 ≔ 80715380156242579087220
Download Help Document
What kind of issue would you like to report? (Optional)
Thank you for submitting feedback on this help document. Your feedback will be used
to improve Maple's help in the future.