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
#***************************************************************************** # Copyright (C) 2005 William Stein <wstein@gmail.com> # Copyright (C) 2007 Martin Albrecht <malb@informatik.uni-bremen.de> # # Distributed under the terms of the GNU General Public License (GPL) # # This code is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU # General Public License for more details. # # The full text of the GPL is available at: # # http://www.gnu.org/licenses/ #*****************************************************************************
from __future__ import absolute_import, division
from cysignals.signals cimport sig_on, sig_off from sage.ext.cplusplus cimport ccrepr, ccreadstr
include 'misc.pxi' include 'decl.pxi'
from cpython.object cimport Py_EQ, Py_NE from sage.rings.integer cimport Integer from sage.misc.superseded import deprecation
from .ntl_ZZ import unpickle_class_value from .ntl_GF2 cimport ntl_GF2
############################################################################## # # ntl_GF2X: Polynomials over GF(2) via NTL # # AUTHORS: # - Martin Albrecht <malb@informatik.uni-bremen.de> # 2006-01: initial version (based on code by William Stein) # - Martin Albrecht <malb@informatik.uni-bremen.de> # 2007-10: adapted to new conventions # ##############################################################################
def GF2XHexOutput(have_hex=None): """ Represent GF2X and GF2E elements in the more compact hexadecimal form to the user.
If no parameter is provided the currently set value will be returned.
INPUT: have_hex if True hex representation will be used
EXAMPLES::
sage: m = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: x = ntl.GF2E([1,0,1,0,1], m) ; x [1 0 1 0 1]
sage: ntl.GF2XHexOutput() ## indirect doctest False sage: ntl.GF2XHexOutput(True) sage: ntl.GF2XHexOutput() True
sage: x 0x51
sage: ntl.GF2XHexOutput(False) sage: x [1 0 1 0 1] """
else:
cdef class ntl_GF2X(object): """ Univariate Polynomials over GF(2) via NTL. """ def __init__(self, x=[]): """ Constructs a new polynomial over GF(2).
A value may be passed to this constructor. If you pass a string to the constructor please note that byte sequences and the hexadecimal notation are little endian. So e.g. '[0 1]' == '0x2' == x.
Input types are ntl.ZZ_px, strings, lists of digits, FiniteFieldElements from extension fields over GF(2), Polynomials over GF(2), Integers, and finite extension fields over GF(2) (uses modulus).
INPUT: x -- value to be assigned to this element. See examples.
OUTPUT: a new ntl.GF2X element
EXAMPLES::
sage: ntl.GF2X(ntl.ZZ_pX([1,1,3],2)) [1 1 1] sage: ntl.GF2X('0x1c') [1 0 0 0 0 0 1 1] sage: ntl.GF2X('[1 0 1 0]') [1 0 1] sage: ntl.GF2X([1,0,1,0]) [1 0 1] sage: ntl.GF2X(GF(2**8,'a').gen()**20) [0 0 1 0 1 1 0 1] sage: ntl.GF2X(GF(2**8,'a')) [1 0 1 1 1 0 0 0 1] sage: ntl.GF2X(2) [0 1] sage: ntl.GF2X(ntl.GF2(1)) [1]
sage: R.<x> = GF(2)[] sage: f = x^5+x^2+1 sage: ntl.GF2X(f) [1 0 1 0 0 1] """
cdef long _x
_x = x GF2XFromBytes(self.x, <unsigned char *>(&_x),sizeof(long)) return
#binary repr, reversed, and "["..."]" added x = x.polynomial().list() # TODO: this is very slow, but we wait until somebody complains
def __reduce__(self): """ EXAMPLES::
sage: f = ntl.GF2X(ntl.ZZ_pX([1,1,3],2)) sage: loads(dumps(f)) == f True sage: f = ntl.GF2X('0x1c') sage: loads(dumps(f)) == f True """
def __repr__(self): """ Return the string representation of self.
EXAMPLES::
sage: ntl.GF2X(ntl.ZZ_pX([1,1,3],2)).__repr__() '[1 1 1]' """
def __mul__(ntl_GF2X self, other): """ EXAMPLES::
sage: f = ntl.GF2X([1,0,1,1]) ; g = ntl.GF2X([0,1]) sage: f*g ## indirect doctest [0 1 0 1 1] """ other = ntl_GF2X(other)
def __truediv__(ntl_GF2X self, b): """ EXAMPLES::
sage: a = ntl.GF2X(4) sage: a / ntl.GF2X(2) [0 1] sage: a / ntl.GF2X(3) Traceback (most recent call last): ... ArithmeticError: self (=[0 0 1]) is not divisible by b (=[1 1]) """ cdef int divisible
b = ntl_GF2X(b)
def __div__(self, other):
def DivRem(ntl_GF2X self, b): """ EXAMPLES::
sage: a = ntl.GF2X(4) sage: a.DivRem( ntl.GF2X(2) ) ([0 1], []) sage: a.DivRem( ntl.GF2X(3) ) ([1 1], [1]) """
b = ntl_GF2X(b)
def __floordiv__(ntl_GF2X self, b): """ EXAMPLES::
sage: a = ntl.GF2X(4) sage: a // ntl.GF2X(2) [0 1] sage: a // ntl.GF2X(3) [1 1] """
b = ntl_GF2X(b)
def __mod__(ntl_GF2X self, b): """ EXAMPLES::
sage: a = ntl.GF2X(4) sage: a % ntl.GF2X(2) [] sage: a % ntl.GF2X(3) [1] """
b = ntl_GF2X(b)
def __sub__(ntl_GF2X self, other): """ EXAMPLES::
sage: f = ntl.GF2X([1,0,1,1]) ; g = ntl.GF2X([0,1]) sage: f - g ## indirect doctest [1 1 1 1] sage: g - f [1 1 1 1] """ other = ntl_GF2X(other)
def __add__(ntl_GF2X self, other): """ EXAMPLES::
sage: f = ntl.GF2X([1,0,1,1]) ; g = ntl.GF2X([0,1,0]) sage: f + g ## indirect doctest [1 1 1 1] """ other = ntl_GF2X(other)
def __neg__(ntl_GF2X self): """ EXAMPLES::
sage: f = ntl.GF2X([1,0,1,1]) sage: -f ## indirect doctest [1 0 1 1] sage: f == -f True """
def __pow__(ntl_GF2X self, long e, ignored): """ EXAMPLES::
sage: f = ntl.GF2X([1,0,1,1]) ; g = ntl.GF2X([0,1,0]) sage: f**3 ## indirect doctest [1 0 1 1 1 0 0 1 1 1] """
def __richcmp__(ntl_GF2X self, other, int op): """ Compare self to other.
EXAMPLES::
sage: f = ntl.GF2X([1,0,1,1]) sage: g = ntl.GF2X([0,1,0]) sage: f == g ## indirect doctest False sage: f == f True sage: g != polygen(GF(2)) False """ raise TypeError("elements of GF(2)[X] are not ordered")
cdef ntl_GF2X b
def __lshift__(ntl_GF2X self, int i): """ Return left shift of self by i bits ( == multiplication by $X^i$).
INPUT: i -- offset/power of X
EXAMPLES::
sage: a = ntl.GF2X(4); a [0 0 1] sage: a << 2 [0 0 0 0 1] """
def __rshift__(ntl_GF2X self, int offset): """ Return right shift of self by i bits ( == floor division by $X^i$).
INPUT: i -- offset/power of X
EXAMPLES::
sage: a = ntl.GF2X(4); a [0 0 1] sage: a >> 1 [0 1] """
def GCD(ntl_GF2X self, other): """ Return GCD of self and other.
INPUT: other -- ntl.GF2X
EXAMPLES::
sage: a = ntl.GF2X(10) sage: b = ntl.GF2X(4) sage: a.GCD(b) [0 1] """
other = ntl_GF2X(other)
def XGCD(ntl_GF2X self, other): """ Return the extended gcd of self and other, i.e., elements r, s, t such that
r = s * self + t * other.
INPUT: other -- ntl.GF2X
EXAMPLES::
sage: a = ntl.GF2X(10) sage: b = ntl.GF2X(4) sage: r,s,t = a.XGCD(b) sage: r == a*s + t*b True
"""
other = ntl_GF2X(other)
def deg(ntl_GF2X self): """ Returns the degree of this polynomial
EXAMPLES::
sage: ntl.GF2X([1,0,1,1]).deg() 3 """
def list(ntl_GF2X self): """ Represents this element as a list of binary digits.
EXAMPLES::
sage: e=ntl.GF2X([0,1,1]) sage: e.list() [0, 1, 1] sage: e=ntl.GF2X('0xff') sage: e.list() [1, 1, 1, 1, 1, 1, 1, 1]
OUTPUT: a list of digits representing the coefficients in this element's polynomial representation """
def bin(ntl_GF2X self): """ Returns binary representation of this element. It is the same as setting \code{ntl.GF2XHexOutput(False)} and representing this element afterwards. However it should be faster and preserves the HexOutput state as opposed to the above code.
EXAMPLES::
sage: e=ntl.GF2X([1,1,0,1,1,1,0,0,1]) sage: e.bin() '[1 1 0 1 1 1 0 0 1]'
OUTPUT: string representing this element in binary digits """
def hex(ntl_GF2X self): """ Return an hexadecimal representation of this element.
It is the same as setting \code{ntl.GF2XHexOutput(True)} and representing this element afterwards. However it should be faster and preserves the HexOutput state as opposed to the above code.
OUTPUT:
string representing this element in hexadecimal
EXAMPLES::
sage: e = ntl.GF2X([1,1,0,1,1,1,0,0,1]) sage: e.hex() '0xb31'
TESTS::
sage: hex(e) doctest:warning...: DeprecationWarning: use the method .hex instead See http://trac.sagemath.org/24514 for details. '0xb31' """
def __hex__(self):
def __hash__(self):
def _sage_(ntl_GF2X self, R=None): """ Returns a Sage polynomial over GF(2) equivalent to this element. If a ring R is provided it is used to construct the polynomial in, otherwise an appropriate ring is generated.
INPUT: self -- GF2X element R -- PolynomialRing over GF(2)
OUTPUT: polynomial in R
EXAMPLES::
sage: f = ntl.GF2X([1,0,1,1,0,1]) sage: f._sage_() x^5 + x^3 + x^2 + 1 sage: f._sage_(PolynomialRing(Integers(2),'y')) y^5 + y^3 + y^2 + 1 """
def coeff(self, int i): """ Return the coefficient of the monomial $X^i$ in self.
INPUT: i -- degree of X
EXAMPLES::
sage: e = ntl.GF2X([0,1,0,1]) sage: e.coeff(0) 0 sage: e.coeff(1) 1 """
def __getitem__(self, int i): """ sage: e = ntl.GF2X([0,1,0,1]) sage: e[0] # indirect doctest 0 sage: e[1] 1 """
def LeadCoeff(self): """ Return the leading coefficient of self. This is always 1 except when self == 0.
EXAMPLES::
sage: e = ntl.GF2X([0,1]) sage: e.LeadCoeff() 1 sage: e = ntl.GF2X(0) sage: e.LeadCoeff() 0 """
def ConstTerm(self): """ Return the constant term of self.
EXAMPLES::
sage: e = ntl.GF2X([1,0,1]) sage: e.ConstTerm() 1 sage: e = ntl.GF2X(0) sage: e.ConstTerm() 0 """
def SetCoeff(self, int i, a): """ Return the constant term of self.
EXAMPLES::
sage: e = ntl.GF2X([1,0,1]); e [1 0 1] sage: e.SetCoeff(1,1) sage: e [1 1 1] """
def __setitem__(self, int i, a): """ sage: e = ntl.GF2X([1,0,1]); e [1 0 1] sage: e[1] = 1 # indirect doctest sage: e [1 1 1] """
def diff(self): """ Differentiate self. sage: e = ntl.GF2X([1,0,1,1,0]) sage: e.diff() [0 0 1] """
def reverse(self, int hi = -2): """ Return reverse of a[0]..a[hi] (hi >= -1) hi defaults to deg(a)
INPUT: hi -- bit position until which reverse is requested
EXAMPLES::
sage: e = ntl.GF2X([1,0,1,1,0]) sage: e.reverse() [1 1 0 1] """
def weight(self): """ Return the number of nonzero coefficients in self.
EXAMPLES::
sage: e = ntl.GF2X([1,0,1,1,0]) sage: e.weight() 3 """
def __int__(self): """ sage: e = ntl.GF2X([1,0,1,1,0]) sage: int(e) Traceback (most recent call last): ... ValueError: cannot convert non-constant polynomial to integer sage: e = ntl.GF2X([1]) sage: int(e) 1 """ else:
def NumBits(self): """ returns number of bits of self, i.e., deg(self) + 1.
EXAMPLES::
sage: e = ntl.GF2X([1,0,1,1,0]) sage: e.NumBits() 4 """
def __len__(self): """ sage: e = ntl.GF2X([1,0,1,1,0]) sage: len(e) 4 """
def NumBytes(self): """ Returns number of bytes of self, i.e., floor((NumBits(self)+7)/8)
EXAMPLES::
sage: e = ntl.GF2X([1,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,1,1]) sage: e.NumBytes() 3 """ |