Coverage for local/lib/python2.7/site-packages/sage/libs/ntl/ntl_lzz_pX.pyx : 73%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
""" ntl_lzz_pX.pyx
Wraps NTL's zz_pX type for SAGE
AUTHORS: - Craig Citro """
#***************************************************************************** # Copyright (C) 2005 William Stein <wstein@gmail.com> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
from __future__ import absolute_import, division
from cysignals.signals cimport sig_on, sig_off
include 'misc.pxi' include 'decl.pxi' from sage.libs.gmp.mpz cimport *
from cpython.object cimport Py_EQ, Py_NE from sage.rings.integer import Integer from sage.rings.integer_ring import IntegerRing from sage.rings.integer cimport Integer from sage.rings.integer_ring cimport IntegerRing_class
from sage.rings.finite_rings.integer_mod cimport IntegerMod_gmp, IntegerMod_int, IntegerMod_int64
from sage.libs.ntl.ntl_lzz_pContext import ntl_zz_pContext from sage.libs.ntl.ntl_lzz_pContext cimport ntl_zz_pContext_class
from sage.libs.ntl.ntl_lzz_p import ntl_zz_p from sage.libs.ntl.ntl_lzz_p cimport ntl_zz_p
ZZ_sage = IntegerRing()
############################################################################## # # zz_pX -- polynomials over the integers modulo p, p small # ##############################################################################
cdef class ntl_zz_pX(object): r""" The class \class{zz_pX} implements polynomial arithmetic modulo $p$, for p smaller than a machine word.
Polynomial arithmetic is implemented using the FFT, combined with the Chinese Remainder Theorem. A more detailed description of the techniques used here can be found in [Shoup, J. Symbolic Comp. 20:363-397, 1995].
Small degree polynomials are multiplied either with classical or Karatsuba algorithms. """ # See ntl_zz_pX.pxd for definition of data members def __init__(self, ls=[], modulus=None): """ EXAMPLES: sage: f = ntl.zz_pX([1,2,5,-9],20) sage: f [1, 2, 5, 11] sage: g = ntl.zz_pX([0,0,0],20); g [] sage: g[10]=5 sage: g [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5] sage: g[10] 5 sage: f = ntl.zz_pX([10^30+1, 10^50+1], 100); f [1, 1] """ raise ValueError("You must specify a modulus.")
cdef long n cdef Py_ssize_t i cdef long temp
else:
#self.c.restore_c() ## We did this in __new__
## the 0 polynomial is just the empty list; ## so in this case, we're done.
if (self.c.p == (<IntegerMod_int>a).__modulus.int32): ## this is slow zz_pX_SetCoeff_long(self.x, i, (<IntegerMod_int>a).ivalue) else: raise ValueError("Mismatched modulus for converting to zz_pX.") if (self.c.p == (<IntegerMod_int64>a).__modulus.int64): ## this is slow zz_pX_SetCoeff_long(self.x, i, (<IntegerMod_int64>a).ivalue) else: raise ValueError("Mismatched modulus for converting to zz_pX.") if (p_sage == (<IntegerMod_gmp>a).__modulus.sageInteger): ## this is slow zz_pX_SetCoeff_long(self.x, i, mpz_get_si((<IntegerMod_gmp>a).value)) else: raise ValueError("Mismatched modulus for converting to zz_pX.") ## we're lucky that python int is no larger than long else:
def __cinit__(self, v=None, modulus=None): #################### WARNING ################### ## Before creating a zz_pX, you must create a ## ## zz_pContext, and restore it. In Python, ## ## the error checking in __init__ will prevent## ## you from constructing a zz_pX ## ## inappropriately. However, from Cython, you## ## could do r = ntl_zz_pX.__new__(ntl_zz_pX) without ## first restoring a zz_pContext, which could ## ## have unfortunate consequences. See _new ## ## defined below for an example of the right ## ## way to short-circuit __init__ (or just call## ## _new in your own code). ## ################################################ elif isinstance(modulus, long): self.c = <ntl_zz_pContext_class>ntl_zz_pContext(modulus) else: try: modulus = int(modulus) except Exception: raise ValueError("%s is not a valid modulus." % modulus) self.c = <ntl_zz_pContext_class>ntl_zz_pContext(modulus)
## now that we've determined the modulus, set that modulus.
def __reduce__(self): """ TESTS: sage: f = ntl.zz_pX([10,10^30+1], 20) sage: f == loads(dumps(f)) True """
def __repr__(self): """ Return the string representation of self.
EXAMPLES: sage: f = ntl.zz_pX([3,5], 17) sage: f.__repr__() '[3, 5]' """
def __getitem__(self, i): """ Return the ith coefficient of f.
EXAMPLES: sage: f = ntl.zz_pX(range(7), 71) sage: f[3] ## indirect doctest 3
sage: f[-5] 0
sage: f[27] 0 """ cdef ntl_zz_p y
def __setitem__(self, i, val): """ Set the ith coefficient of self to val. If i is out of range, raise an exception.
EXAMPLES: sage: f = ntl.zz_pX([], 7) sage: f[3] = 2 ; f [0, 0, 0, 2] sage: f[-1] = 5 Traceback (most recent call last): ... ValueError: index (=-1) is out of range """
cdef ntl_zz_pX _new(self): """ Quick and dirty method for creating a new object with the same zz_pContext as self.
EXAMPLES: sage: f = ntl.zz_pX([1], 20) sage: f.square() ## indirect doctest [1] """ cdef ntl_zz_pX y
def __add__(ntl_zz_pX self, other): """ Return self + other.
EXAMPLES: sage: ntl.zz_pX(range(5),20) + ntl.zz_pX(range(6),20) ## indirect doctest [0, 2, 4, 6, 8, 5] sage: ntl.zz_pX(range(5),20) + ntl.zz_pX(range(6),50) Traceback (most recent call last): ... ValueError: arithmetic operands must have the same modulus. """ cdef ntl_zz_pX y other = ntl_zz_pX(other, modulus=self.c)
def __sub__(ntl_zz_pX self, other): """ Return self - other.
EXAMPLES: sage: ntl.zz_pX(range(5),32) - ntl.zz_pX(range(6),32) [0, 0, 0, 0, 0, 27] sage: ntl.zz_pX(range(5),20) - ntl.zz_pX(range(6),50) ## indirect doctest Traceback (most recent call last): ... ValueError: arithmetic operands must have the same modulus. """ cdef ntl_zz_pX y other = ntl_zz_pX(other, modulus=self.c)
def __mul__(ntl_zz_pX self, other): """ EXAMPLES: sage: ntl.zz_pX(range(5),20) * ntl.zz_pX(range(6),20) ## indirect doctest [0, 0, 1, 4, 10, 0, 10, 14, 11] sage: ntl.zz_pX(range(5),20) * ntl.zz_pX(range(6),50) Traceback (most recent call last): ... ValueError: arithmetic operands must have the same modulus. """ cdef ntl_zz_pX y other = ntl_zz_pX(other, modulus=self.c)
def __truediv__(ntl_zz_pX self, other): """ Compute quotient self / other, if the quotient is a polynomial. Otherwise an Exception is raised.
EXAMPLES: sage: f = ntl.zz_pX([1,2,3],17) * ntl.zz_pX([4,5],17)**2 sage: g = ntl.zz_pX([4,5],17) sage: f/g ## indirect doctest [4, 13, 5, 15] sage: ntl.zz_pX([1,2,3],17) * ntl.zz_pX([4,5],17) [4, 13, 5, 15]
sage: f = ntl.zz_pX(range(10),17); g = ntl.zz_pX([-1,0,1],17) sage: f/g Traceback (most recent call last): ... ArithmeticError: self (=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) is not divisible by other (=[16, 0, 1]) sage: ntl.zz_pX(range(5),20) / ntl.zz_pX(range(6),50) Traceback (most recent call last): ... ValueError: arithmetic operands must have the same modulus. """ cdef long divisible cdef ntl_zz_pX q other = ntl_zz_pX(other, modulus=self.c)
def __div__(self, other):
def __mod__(ntl_zz_pX self, other): """ Given polynomials a, b in ZZ[X], there exist polynomials q, r in QQ[X] such that a = b*q + r, deg(r) < deg(b). This function returns q if q lies in ZZ[X], and otherwise raises an Exception.
EXAMPLES: sage: f = ntl.zz_pX([2,4,6],17); g = ntl.zz_pX([2],17) sage: f % g ## indirect doctest []
sage: f = ntl.zz_pX(range(10),17); g = ntl.zz_pX([-1,0,1],17) sage: f % g [3, 8] """ cdef ntl_zz_pX y other = ntl_zz_pX(other, modulus=self.c) raise ValueError("arithmetic operands must have the same modulus.")
def __pow__(ntl_zz_pX self, long n, ignored): """ Return the n-th nonnegative power of self.
EXAMPLES: sage: g = ntl.zz_pX([-1,0,1],20) sage: g**10 ## indirect doctest [1, 0, 10, 0, 5, 0, 0, 0, 10, 0, 8, 0, 10, 0, 0, 0, 5, 0, 10, 0, 1] """ raise ValueError("Only positive exponents allowed.")
def quo_rem(ntl_zz_pX self, ntl_zz_pX right): """ Returns the quotient and remainder when self is divided by right.
Specifically, this return r, q such that $self = q * right + r$
EXAMPLES: sage: f = ntl.zz_pX(range(7), 19) sage: g = ntl.zz_pX([2,4,6], 19) sage: f // g [1, 1, 15, 16, 1] sage: f % g [17, 14] sage: f.quo_rem(g) ([1, 1, 15, 16, 1], [17, 14]) sage: (f // g) * g + f % g [0, 1, 2, 3, 4, 5, 6] """
def __floordiv__(ntl_zz_pX self, ntl_zz_pX right): """ Returns the whole part of $self / right$.
EXAMPLES: sage: f = ntl.zz_pX(range(10), 19); g = ntl.zz_pX([1]*5, 19) sage: f // g ## indirect doctest [8, 18, 18, 18, 18, 9]
"""
def __lshift__(ntl_zz_pX self, long n): """ Shifts this polynomial to the left, which is multiplication by $x^n$.
EXAMPLES: sage: f = ntl.zz_pX([2,4,6], 17) sage: f << 2 ## indirect doctest [0, 0, 2, 4, 6] """
def __rshift__(ntl_zz_pX self, long n): """ Shifts this polynomial to the right, which is division by $x^n$ (and truncation).
EXAMPLES: sage: f = ntl.zz_pX([1,2,3], 17) sage: f >> 2 ## indirect doctest [3] """
def diff(self): """ The formal derivative of self.
EXAMPLES: sage: f = ntl.zz_pX(range(10), 17) sage: f.diff() [1, 4, 9, 16, 8, 2, 15, 13, 13] """
def reverse(self): """ Returns self with coefficients reversed, i.e. $x^n self(x^{-n})$.
EXAMPLES: sage: f = ntl.zz_pX([2,4,6], 17) sage: f.reverse() [6, 4, 2] """
def __neg__(self): """ Return the negative of self. EXAMPLES: sage: f = ntl.zz_pX([2,0,0,1],20) sage: -f [18, 0, 0, 19] """ cdef ntl_zz_pX y
def __richcmp__(ntl_zz_pX self, other, int op): """ Compare self to other.
EXAMPLES::
sage: f = ntl.zz_pX([1,2,3],20) sage: g = ntl.zz_pX([1,2,3,0],20) sage: f == g True sage: g = ntl.zz_pX([0,1,2,3],20) sage: f == g False sage: f != [0] True """
raise TypeError("polynomials are not ordered")
cdef ntl_zz_pX b
def list(self): """ Return list of entries as a list of python ints.
EXAMPLES: sage: f = ntl.zz_pX([23, 5,0,1], 10) sage: f.list() [3, 5, 0, 1] sage: type(f.list()[0]) <... 'int'> """ cdef long i
def degree(self): """ Return the degree of this polynomial. The degree of the 0 polynomial is -1.
EXAMPLES: sage: f = ntl.zz_pX([5,0,1],50) sage: f.degree() 2 sage: f = ntl.zz_pX(range(100),50) sage: f.degree() 99 sage: f = ntl.zz_pX([],10) sage: f.degree() -1 sage: f = ntl.zz_pX([1],77) sage: f.degree() 0 """
def leading_coefficient(self): """ Return the leading coefficient of this polynomial.
EXAMPLES: sage: f = ntl.zz_pX([3,6,9],19) sage: f.leading_coefficient() 9 sage: f = ntl.zz_pX([],21) sage: f.leading_coefficient() 0 """
def constant_term(self): """ Return the constant coefficient of this polynomial.
EXAMPLES: sage: f = ntl.zz_pX([3,6,9],127) sage: f.constant_term() 3 sage: f = ntl.zz_pX([], 12223) sage: f.constant_term() 0 """
def square(self): """ Return f*f.
EXAMPLES: sage: f = ntl.zz_pX([-1,0,1],17) sage: f*f [1, 0, 15, 0, 1] """
def truncate(self, long m): """ Return the truncation of this polynomial obtained by removing all terms of degree >= m.
EXAMPLES: sage: f = ntl.zz_pX([1,2,3,4,5],70) sage: f.truncate(3) [1, 2, 3] sage: f.truncate(8) [1, 2, 3, 4, 5] sage: f.truncate(1) [1] sage: f.truncate(0) [] sage: f.truncate(-1) [] sage: f.truncate(-5) [] """ else:
def multiply_and_truncate(self, ntl_zz_pX other, long m): """ Return self*other but with terms of degree >= m removed.
EXAMPLES: sage: f = ntl.zz_pX([1,2,3,4,5],20) sage: g = ntl.zz_pX([10],20) sage: f.multiply_and_truncate(g, 2) [10] sage: g.multiply_and_truncate(f, 2) [10] """ y.x = zz_pX_zero() else:
def square_and_truncate(self, long m): """ Return self*self but with terms of degree >= m removed.
EXAMPLES: sage: f = ntl.zz_pX([1,2,3,4,5],20) sage: f.square_and_truncate(4) [1, 4, 10] sage: (f*f).truncate(4) [1, 4, 10] """ y.x = zz_pX_zero() else:
def invert_and_truncate(self, long m): """ Compute and return the inverse of self modulo $x^m$. The constant term of self must be 1 or -1.
EXAMPLES: sage: f = ntl.zz_pX([1,2,3,4,5,6,7],20) sage: f.invert_and_truncate(20) [1, 18, 1, 0, 0, 0, 0, 8, 17, 2, 13, 0, 0, 0, 4, 0, 17, 10, 9] sage: g = f.invert_and_truncate(20) sage: g * f [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 4, 4, 3] """ raise ArithmeticError("m (=%s) must be positive" % m) raise ArithmeticError("The constant term of self must be 1 or -1.")
y.x = zz_pX_zero() else:
def is_zero(self): """ Return True exactly if this polynomial is 0.
EXAMPLES: sage: f = ntl.zz_pX([0,0,0,20],5) sage: f.is_zero() True sage: f = ntl.zz_pX([0,0,1],30) sage: f [0, 0, 1] sage: f.is_zero() False """
def is_one(self): """ Return True exactly if this polynomial is 1.
EXAMPLES: sage: f = ntl.zz_pX([1,1],101) sage: f.is_one() False sage: f = ntl.zz_pX([1],2) sage: f.is_one() True """
def is_monic(self): """ Return True exactly if this polynomial is monic.
EXAMPLES: sage: f = ntl.zz_pX([2,0,0,1],17) sage: f.is_monic() True sage: g = f.reverse() sage: g.is_monic() False sage: g [1, 0, 0, 2] sage: f = ntl.zz_pX([1,2,0,3,0,2],717) sage: f.is_monic() False """ return False
def set_x(self): """ Set this polynomial to the monomial "x".
EXAMPLES: sage: f = ntl.zz_pX([],177) sage: f.set_x() sage: f [0, 1] sage: g = ntl.zz_pX([0,1],177) sage: f == g True
Though f and g are equal, they are not the same objects in memory: sage: f is g False
"""
def is_x(self): """ True if this is the polynomial "x".
EXAMPLES: sage: f = ntl.zz_pX([],100) sage: f.set_x() sage: f.is_x() True sage: f = ntl.zz_pX([0,1],383) sage: f.is_x() True sage: f = ntl.zz_pX([1],38) sage: f.is_x() False """
def clear(self): """ Reset this polynomial to 0. Changes this polynomial in place.
EXAMPLES: sage: f = ntl.zz_pX([1,2,3],17) sage: f [1, 2, 3] sage: f.clear() sage: f [] """
def preallocate_space(self, long n): """ Pre-allocate spaces for n coefficients. The polynomial that f represents is unchanged. This is useful if you know you'll be setting coefficients up to n, so memory isn't re-allocated as the polynomial grows. (You might save a millisecond with this function.)
EXAMPLES: sage: f = ntl.zz_pX([1,2,3],17) sage: f.preallocate_space(20) sage: f [1, 2, 3] sage: f[10]=5 # no new memory is allocated sage: f [1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 5] """
def make_zz_pX(L, context): """ For unpickling.
TESTS: sage: f = ntl.zz_pX(range(16), 12) sage: loads(dumps(f)) == f True """ |