LinearAlgebra[Modular] - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Parameters

Description

Examples

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,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+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;

p97

(1)

An example of three polynomials with a known GCD.

G := randpoly(x,degree=2,coeffs=rand(0..p-1));

G92x2+44x+95

(2)

Ac := randpoly(x,degree=2, coeffs=rand(0..p-1)):  A := expand(G*Ac);

A460x4+5556x3+6983x2+7402x+4085

(3)

Bc := randpoly(x,degree=3, coeffs=rand(0..p-1)):  B := expand(G*Bc);

B3404x5+7884x4+8899x3+16344x2+6650x+9025

(4)

Cc := randpoly(x,degree=1, coeffs=rand(0..p-1)):  C := expand(G*Cc);

C1472x3+8892x2+5436x+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))]];

cfs4085,7402,6983,5556,460,9025,6650,16344,8899,7884,3404,8455,5436,8892,1472

(6)

M := Mod(p,cfs,float[8]);

M11.30.96.27.72.0.4.54.48.72.27.9.16.4.65.17.0.0.

(7)

gdeg := MatGcd(p,M,3):

M,gdeg;

95.44.92.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.,2

(8)

g := add(trunc(M[1,i+1])*x^i,i=0..gdeg);

g92x2+44x+95

(9)

modp(Expand(G/lcoeff(G,x)*lcoeff(g,x)),p);

92x2+44x+95

(10)

An example of a trivial GCD.

A := randpoly(x,degree=5);

A62x582x4+80x344x2+71x17

(11)

B := randpoly(x,degree=4);

B75x410x37x240x+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[]);

M80715380156242579087220

(13)

MatGcd(p,M,2);

0

(14)

M;

7500000000000

(15)

See Also

coeff

Expand

LinearAlgebra/Details

LinearAlgebra[Modular]

LinearAlgebra[Modular][Mod]

randpoly

seq

trunc