Opened 8 years ago

Last modified 6 weeks ago

## #17674 new defect

# xgcd is badly named on non PID domains

Reported by: | vdelecroix | Owned by: | |
---|---|---|---|

Priority: | major | Milestone: | |

Component: | basic arithmetic | Keywords: | |

Cc: | jdemeyer, bruno | Merged in: | |

Authors: | Reviewers: | ||

Report Upstream: | N/A | Work issues: | |

Branch: | Commit: | ||

Dependencies: | Stopgaps: |

### Description

Over non PID domains, the method xgcd might not (and can not in general) return the gcd as its first argument

sage: x = polygen(ZZ) sage: (x+2).gcd(x+4) # no common factor but... 1 sage: (x+2).xgcd(x+4) # ... the ideal (x+2, x+4) is not principal (2, -1, 1)

See this sage-devel thread where it was suggested to change the method name to `pseudo_xgcd`

or `_resultant_xgcd`

.

See also #17671 that fix some compatibility issues for gcd/xgcd over PID.

### Change History (6)

### comment:1 Changed 8 years ago by

### comment:2 follow-up: 3 Changed 8 years ago by

Let me repeat and extend as a comment my remarks on sage-devel, concerning the "literature":

- In almost all books in which I've checked, the extended Euclidean algorithm is only defined for polynomials over fields, and not over rings. This books include
- Modern Computer Algebra (von zur Gathen and Gerhard);
- The Art of Computer Programming: Semi-Numerical Algorithms (Knuth);
- A Computational Introduction to Number Theory and Algebra (Shoup);
- Fundamental problems in algorithmic algebra (Yap).

- A course in computational number theory (Cohen)

`g*r`

,`s`

and`t`

where`g`

is the GCD and`r`

the resultant, and`s`

and`t`

satisfy`g*r = s*a+t*b`

for inputs`a`

and`b`

.

- For softwares and libraries (inputs are two univariate polynomials
`a`

and`b`

over the integers):- Flint:
`fmpz_poly_xgcd`

computes`r`

,`s`

and`t`

where`r=res(a,b)`

and`r=s*a+t*b`

; - NTL: idem Flint;
- Mathemagix: the
`xgcd`

-like function returns an error; - Maple17: the function
`gcdex`

works as if`a`

and`b`

were defined over the rational numbers; - Mathematica (? tested via WolframAlpha): idem Maple17.

- Flint:

Now for my opinion:

- My preferred solution is the one chosen by Flint and NTL, keeping the name
`xgcd`

; - If the consensus is to change the name, I would be greatly in favor of a name beginning with
`xgcd_...`

for completion considerations.

### comment:3 follow-up: 4 Changed 8 years ago by

Replying to bruno:

- My preferred solution is the one chosen by Flint and NTL, keeping the name
`xgcd`

;

FLINT *does not* use the name `xgcd`

, it uses the name `fmpz_poly_xgcd`

. This may look like nitpicking, but it's really not. The FLINT call is explicit that it's for `fmpz_poly`

: polynomials over `ZZ`

. When you use the generic `xgcd`

name to mean both the "real" xgcd and the "fake" xgcd-times-resultant depending on the input, that's confusing.

### comment:4 Changed 8 years ago by

Replying to jdemeyer:

Replying to bruno:

- My preferred solution is the one chosen by Flint and NTL, keeping the name
`xgcd`

;FLINT

does notuse the name`xgcd`

, it uses the name`fmpz_poly_xgcd`

. This may look like nitpicking, but it's really not. The FLINT call is explicit that it's for`fmpz_poly`

: polynomials over`ZZ`

. When you use the generic`xgcd`

name to mean both the "real" xgcd and the "fake" xgcd-times-resultant depending on the input, that's confusing.

In Sage you have the object-oriented syntax `object.method()`

while in Flint there is some kind of naming convention `type_function()`

. And you have `fmpz_poly_xgcd`

exactly in the same way as you have `fmpz_xgcd`

or `fmpq_poly_xgcd`

, so one could argue, in the same way as you argue for the `xgcd`

function in Sage, that a user expects these functions to implement the same mathematical function in the three cases. I am not sure (even if you think so) that the situation in Sage is much more confusing than the situation in Flint. Actually, I do not think it is really confusing in any case.

### comment:5 Changed 8 years ago by

Component: | PLEASE CHANGE → basic arithmetic |
---|---|

Type: | PLEASE CHANGE → defect |

### comment:6 Changed 6 weeks ago by

Milestone: | sage-6.5 |
---|

**Note:**See TracTickets for help on using tickets.

Wikipedia is formal about the definition of xgcd. But there is a mention of

in the section Polynomial extended Euclidean algorithm. See also the page on Bézout identity

magma defines xgcd only for univariate polynomials over fields or residue class ring with prime modulus.