Previous Up Next

2.31.13  GCD in ℤ/pℤ[x] : gcd

gcd takes as arguments two polynomials with coefficients in ℤ/pℤ (p must be prime).
gcd returns the GCD of these polynomials computed in ℤ/pℤ[x] (see also 2.25.7 for polynomials with non modular coefficients).
Input :

gcd((2*x^2+5)%13,(5*x^2+2*x-3)%13)

Output :

(-4%13)*x+5%13

Input :

gcd((x^2+2*x+1,x^2-1)) mod 5)

Output :

x%5

Note the difference with a gcd computation in ℤ[X] followed by a reduction modulo 5, input:

gcd(x^2+2*x+1,x^2-1) mod 5

Output :

1

Previous Up Next