Opened 5 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 (Commits) 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 5 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

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

• Milestone changed from sage-6.3 to sage-6.4

### comment:3 Changed 3 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 2 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 2 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 13 months 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)
(, , )
```

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

### comment:7 Changed 13 months ago by lftabera

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

### comment:8 Changed 12 months ago by vdelecroix

• Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

Note: See TracTickets for help on using tickets.