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 . 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 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
|
|
>
|
|
>
|
|
| (1) |
An example of three polynomials with a known GCD.
>
|
|
| (2) |
>
|
|
| (3) |
>
|
|
| (4) |
>
|
|
| (5) |
>
|
|
| (6) |
>
|
|
| (7) |
>
|
|
>
|
|
| (8) |
>
|
|
| (9) |
>
|
|
| (10) |
An example of a trivial GCD.
>
|
|
| (11) |
>
|
|
| (12) |
>
|
|
>
|
|
| (13) |
>
|
|
| (14) |
>
|
|
| (15) |
|
|
Download Help Document
Was this information helpful?