Opened 5 years ago

Last modified 9 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 10 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 10 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 9 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.