Opened 7 years ago

# Dense polynomials over Z/nZ , with n composite and using NTL, failed to execute inverse_mod

Reported by: Owned by: bouvier major sage-8.4 basic arithmetic Mark Saaltink N/A u/msaaltink/dense_polynomials_over_z_nz___with_n_composite_and_using_ntl__failed_to_execute_inverse_mod 87499b24aa4694f1425ba1ee3f1af8a3b791c636

### Description

In sage 6.0, dense polynomials over Z/nZ with n composite raise an AttributeError? about missing attribute xgcd when inverse_mod is called. Here is an example:

```sage: K.<t> = PolynomialRing(IntegerModRing(42), 't', implementation='NTL')
sage: L.<y> = PolynomialRing(IntegerModRing(42), 'y', implementation='FLINT')
sage: M.<x> = PolynomialRing(IntegerModRing(5), 'x', implementation='NTL')
sage: (x^2+1).inverse_mod(x^2)
1
sage: (y^2+1).inverse_mod(y^2)
1
sage: (t^2+1).inverse_mod(t^2)
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-71-4ae1aed5e4de> in <module>()
----> 1 (t**Integer(2)+Integer(1)).inverse_mod(t**Integer(2))

/usr/local/sage-6.0-x86_64-Linux/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_element.so in sage.rings.polynomial.polynomial_element.Polynomial.inverse_mod (sage/rings/polynomial/polynomial_element.c:11456)()

/usr/local/sage-6.0-x86_64-Linux/local/lib/python2.7/site-packages/sage/structure/element.so in sage.structure.element.Element.__getattr__ (sage/structure/element.c:3873)()

/usr/local/sage-6.0-x86_64-Linux/local/lib/python2.7/site-packages/sage/structure/misc.so in sage.structure.misc.getattr_from_other_class (sage/structure/misc.c:1696)()

AttributeError: 'sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modn_ntl_zz' object has no attribute 'xgcd'

```

This works for polynomials ring over Z/nZ that use FLINT (so only for small n) or that use NTL but with prime n. The buggy behavior is that sage indicates that inverse_mod attribute should exists :

```sage: p = t^2+1
sage: p.inverse_mod?
Type:       builtin_function_or_method
String Form:<built-in method inverse_mod of sage.rings.polynomial.polynomial_modn_dense_ntl.Polynomial_dense_modn_ntl_zz object at 0x2c488de0>
Definition: p.inverse_mod(a, m)
Docstring:
Inverts the polynomial a with respect to m, or raises a ValueError
if no such inverse exists. The parameter m may be either a single
polynomial or an ideal (for consistency with inverse_mod in other
rings).

EXAMPLES:

sage: S.<t> = QQ[]
sage: f = inverse_mod(t^2 + 1, t^3 + 1); f
-1/2*t^2 - 1/2*t + 1/2
sage: f * (t^2 + 1) % (t^3 + 1)
1
sage: f = t.inverse_mod((t+1)^7); f
-t^6 - 7*t^5 - 21*t^4 - 35*t^3 - 35*t^2 - 21*t - 7
sage: (f * t) + (t+1)^7
1
sage: t.inverse_mod(S.ideal((t + 1)^7)) == f
True

This also works over inexact rings, but note that due to rounding
error the product may not always exactly equal the constant
polynomial 1 and have extra terms with coefficients close to zero.

sage: R.<x> = RDF[]
sage: epsilon = RDF(1).ulp()*50   # Allow an error of up to 50 ulp
sage: f = inverse_mod(x^2 + 1, x^5 + x + 1); f
0.4*x^4 - 0.2*x^3 - 0.4*x^2 + 0.2*x + 0.8
sage: poly = f * (x^2 + 1) % (x^5 + x + 1)
sage: # Remove noisy zero terms:
sage: parent(poly)([ 0.0 if abs(c)<=epsilon else c for c in poly.coeffs() ])
1.0
sage: f = inverse_mod(x^3 - x + 1, x - 2); f
0.142857142857
sage: f * (x^3 - x + 1) % (x - 2)
1.0
sage: g = 5*x^3+x-7; m = x^4-12*x+13; f = inverse_mod(g, m); f
-0.0319636125...*x^3 - 0.0383269759...*x^2 - 0.0463050900...*x + 0.346479687...
sage: poly = f*g % m
sage: # Remove noisy zero terms:
sage: parent(poly)([ 0.0 if abs(c)<=epsilon else c for c in poly.coeffs() ])
1.0

ALGORITHM: Solve the system as + mt = 1, returning s as the inverse
of a mod m.

Uses the Euclidean algorithm for exact rings, and solves a linear
system for the coefficients of s and t for inexact rings (as the
Euclidean algorithm may not converge in that case).

AUTHORS:

```

Cyril

### comment:1 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:2 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:3 Changed 5 years ago by kedlaya

For the record, when I try this in 7.3, the error reported is different (but this doesn't change the underlying issue with the documentation):

```...
sage: sage: (t^2+1).inverse_mod(t^2)
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-8-4ae1aed5e4de> in <module>()
----> 1 (t**Integer(2)+Integer(1)).inverse_mod(t**Integer(2))

/home/kedlaya/sage-complete/src/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial.inverse_mod (/home/kedlaya/sage-complete/src/build/cythonized/sage/rings/polynomial/polynomial_element.c:14109)()
1346         if a.parent().is_exact():
1347             # use xgcd
-> 1348             g, s, _ = a.xgcd(m)
1349             if g == 1:
1350                 return s

/home/kedlaya/sage-complete/src/sage/structure/element.pyx in sage.structure.element.NamedBinopMethod.__call__ (/home/kedlaya/sage-complete/src/build/cythonized/sage/structure/element.c:26637)()
3438                 return getattr(x, self._name)(y, **kwds)
3439         else:
-> 3440             return self._func(x,y, **kwds)
3441
3442     def __get__(self, obj, objtype):

/home/kedlaya/sage-complete/src/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial.xgcd (/home/kedlaya/sage-complete/src/build/cythonized/sage/rings/polynomial/polynomial_element.c:63301)()
7359             return self.base_ring()._xgcd_univariate_polynomial(self, other)
7360         else:
-> 7361             raise NotImplementedError("%s does not provide an xgcd implementation for univariate polynomials"%self.base_ring())
7362
7363     def variables(self):

NotImplementedError: Ring of integers modulo 42 does not provide an xgcd implementation for univariate polynomials
```

### comment:4 Changed 4 years ago by msaaltink

• Branch set to u/msaaltink/dense_polynomials_over_z_nz___with_n_composite_and_using_ntl__failed_to_execute_inverse_mod

### comment:5 Changed 4 years ago by msaaltink

• Authors set to Mark Saaltink
• Commit set to 87499b24aa4694f1425ba1ee3f1af8a3b791c636
• Status changed from new to needs_review

New commits:

 ​87499b2 `Fix inverse_mod for univariate polynomials over ZZ mod n for composite n.`

### comment:6 Changed 3 years ago by lftabera

ntl has its own implementation of invmod, so we use should use that, note also that ntl allows to use xgcd ever for composite n.

```sage: from sage.libs.ntl.ntl_ZZ_pX import ntl_ZZ_pContext, ntl_ZZ_pX
sage: c = ntl_ZZ_pContext(42)
sage: f = ntl_ZZ_pX([1, 0, 1],c)
sage: g = ntl_ZZ_pX([0, 0, 1],c)
sage: f.xgcd(g)
([1], [1], [41])
```

there is also invmod but it seems that does not work right now in my computer...

### comment:7 Changed 3 years ago by lftabera

• Milestone changed from sage-6.4 to sage-8.3
• Status changed from needs_review to needs_work

### comment:8 Changed 3 years ago by vdelecroix

• Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

### comment:9 Changed 3 weeks ago by gh-maple3142

Calculating xgcd of polynomials using NTL implementation still doesn't work in Sage 9.2.

Code:

```print(version())
K.<t> = PolynomialRing(IntegerModRing(42), 't', implementation='NTL')
print((t^2+1).inverse_mod(t^2))
```

Output:

```SageMath version 9.2, Release Date: 2020-10-24
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-1-b06a1f7d9362> in <module>
1 print(version())
2 K = PolynomialRing(IntegerModRing(Integer(42)), 't', implementation='NTL', names=('t',)); (t,) = K._first_ngens(1)
----> 3 print((t**Integer(2)+Integer(1)).inverse_mod(t**Integer(2)))

/home/sc_serv/sage/local/lib/python3.8/site-packages/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial.inverse_mod (build/cythonized/sage/rings/polynomial/polynomial_element.c:15403)()
1490         if a.parent().is_exact():
1491             # use xgcd
-> 1492             g, s, _ = a.xgcd(m)
1493             if g == 1:
1494                 return s

/home/sc_serv/sage/local/lib/python3.8/site-packages/sage/structure/element.pyx in sage.structure.element.coerce_binop.new_method (build/cythonized/sage/structure/element.c:27687)()
4347     def new_method(self, other, *args, **kwargs):
4348         if have_same_parent(self, other):
-> 4349             return method(self, other, *args, **kwargs)
4350         else:
4351             a, b = coercion_model.canonical_coercion(self, other)

/home/sc_serv/sage/local/lib/python3.8/site-packages/sage/rings/polynomial/polynomial_element.pyx in sage.rings.polynomial.polynomial_element.Polynomial.xgcd (build/cythonized/sage/rings/polynomial/polynomial_element.c:70376)()
8503             return self.base_ring()._xgcd_univariate_polynomial(self, other)
8504         else:
-> 8505             raise NotImplementedError("%s does not provide an xgcd implementation for univariate polynomials"%self.base_ring())
8506
8507     def rational_reconstruct(self, m, n_deg=None, d_deg=None):

NotImplementedError: Ring of integers modulo 42 does not provide an xgcd implementation for univariate polynomials
```
Note: See TracTickets for help on using tickets.