Open
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
Component: basic arithmetic
Author: Mark Saaltink
Branch/Commit: u/msaaltink/dense_polynomials_over_z_nz___with_n_composite_and_using_ntl__failed_to_execute_inverse_mod @ 87499b2
Issue created by migration from https://trac.sagemath.org/ticket/15788