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

[cyrilbouvier]

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:

   * Robert Bradshaw (2007-05-31)

Cyril

Component: basic arithmetic

Author: Mark Saaltink

Branch/Commit: u/msaaltink/dense_polynomials_over_z_nz_with_n_composite_and_using_ntlfailed_to_execute_inverse_mod @ 87499b2

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

[kedlaya]

comment:3

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

[0adfa02f-507d-46c6-aa3b-f2437a2a5873]

Branch: u/msaaltink/dense_polynomials_over_z_nz_with_n_composite_and_using_ntlfailed_to_execute_inverse_mod

[0adfa02f-507d-46c6-aa3b-f2437a2a5873]

Author: Mark Saaltink

[0adfa02f-507d-46c6-aa3b-f2437a2a5873]

Commit: 87499b2

[0adfa02f-507d-46c6-aa3b-f2437a2a5873]

New commits:

87499b2

Fix inverse_mod for univariate polynomials over ZZ mod n for composite n.

[lftabera]

comment:6

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...

[videlec]

comment:8

update milestone 8.3 -> 8.4

[e6c7601e-055c-4fdb-9890-a4854e9de483]

comment:9

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