xgcd result violates the documentation

[sagetrac-msaaltink]

In its documentation, xgcd(a,b) promises to return a triple "(g,s,t)" such that g = sa + tb (although it notes that we may not have g = gcd(a,b) when they belong to a ring that is not a PID). We do not always get this equality; here is an example in sage-7.5.1:

sage: _.<x> = Integers(4)[]
sage: a = x - 1
sage: b = 2*x + 1
sage: g,s,t = xgcd(a,b); g,s,t
(2,1,3)
sage: g == a*s + b*t
False
sage: a.resultant(b)
3

It is difficult to know how g=2 arises here! The documentation for a.xgcd, which no doubt gets called here, is less clear, saying only "Computes extended gcd of self and other" without giving any guarantees.

In particular in cases where the ideal (a,b) is the whole ring so that b should have an inverse mod a, this can make the computation of inverse_mod fail:

sage: _.<x> = Integers(4)[]
sage: a = x^2 + x + 1
sage: b = 2*x + 1
sage: g,s,t = xgcd(a,b); g,s,t
(1, 1, 3*x)
sage: a*s + b*t
3*x^2 + 1
sage: b.inverse_mod(a)
3*x
sage: (b.inverse_mod(a) * b) % a
x + 2
sage: b*b
1

So while b has an inverse (mod anything, in this ring), inverse_mod does not compute it.

There has been prior discussion over xgcd in rings that are not PIDs, such as we have here, in #17674 and https://groups.google.com/forum/#!topic/sage-devel/JV8fCPUqTzo, and related issues with inverse_mod have been noted before in #15788.

Component: algebra

Keywords: xgcd, inverse_mod, bezout coefficients

Author: Mark Saaltink

Issue created by migration from https://trac.sagemath.org/ticket/22237

[defeo]

comment:1

This just popped up again in this StackOverflow question: https://stackoverflow.com/questions/48777337/.

Here's another very basic example

sage: _.<a> = Zmod(4)[]
sage: gcd(a^2 - 1, (a-1)^2)
1
sage: xgcd(a^2 - 1, (a-1)^2)
(1, 3*a, a + 2)

There's tons of people out there wanting to use Sage for playing with lattice-based crypto. We should do something about this (although I know it is quite painful to get gcds right for non-PIDs).