Opened 5 years ago

Last modified 7 months ago

#15788 needs_work defect

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

Reported by: bouvier Owned by:
Priority: major Milestone: sage-8.4
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Mark Saaltink Reviewers:
Report Upstream: N/A Work issues:
Branch: u/msaaltink/dense_polynomials_over_z_nz___with_n_composite_and_using_ntl__failed_to_execute_inverse_mod (Commits) Commit: 87499b24aa4694f1425ba1ee3f1af8a3b791c636
Dependencies: Stopgaps:

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:

   * Robert Bradshaw (2007-05-31)


Cyril

Change History (8)

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:

87499b2Fix inverse_mod for univariate polynomials over ZZ mod n for composite n.

comment:6 Changed 8 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)
([1], [1], [41])

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

comment:7 Changed 8 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 7 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.