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> # # 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/ #*****************************************************************************
############################################################################## # # ntl_mat_GF2E: Matrices over the GF(2**x) via NTL # # AUTHORS: # - Martin Albrecht <malb@informatik.uni-bremen.de> # 2006-01: initial version (based on code by William Stein) # ############################################################################## from __future__ import absolute_import
from cysignals.signals cimport sig_on, sig_off from sage.ext.cplusplus cimport ccrepr
include 'misc.pxi' include 'decl.pxi'
from cpython.object cimport Py_EQ, Py_NE from .ntl_GF2E cimport ntl_GF2E from .ntl_GF2EContext import ntl_GF2EContext from .ntl_GF2EContext cimport ntl_GF2EContext_class from sage.rings.integer cimport Integer from sage.misc.randstate cimport randstate, current_randstate
from sage.libs.ntl.ntl_ZZ import unpickle_class_args
cdef class ntl_mat_GF2E(object): r""" The \class{mat_GF2E} class implements arithmetic with matrices over $GF(2**x)$. """ def __init__(self, modulus = None, nrows=0, ncols=0, v=None): """ Constructs a matrix over ntl.GF2E.
INPUT: modulus -- GF2E context nrows -- number of rows ncols -- number of columns v -- either a list or a matrix over GF(2^x)
EXAMPLES::
sage: k.<a> = GF(2^4) sage: ctx = ntl.GF2EContext(k) sage: ntl.GF2XHexOutput(1) sage: ntl.mat_GF2E(ctx, 5,5, [0..24]) [[0x0 0x1 0x2 0x3 0x4] [0x5 0x6 0x7 0x8 0x9] [0xa 0xb 0xc 0xd 0xe] [0xf 0x3 0x2 0x1 0x0] [0x7 0x6 0x5 0x4 0xb] ] sage: ntl.mat_GF2E(ctx, 5,5) [[0x0 0x0 0x0 0x0 0x0] [0x0 0x0 0x0 0x0 0x0] [0x0 0x0 0x0 0x0 0x0] [0x0 0x0 0x0 0x0 0x0] [0x0 0x0 0x0 0x0 0x0] ] sage: A= matrix(k,5,5,[k.fetch_int(_%(2^4)) for _ in range(25)]) sage: ntl.mat_GF2E(ctx, A) [[0x0 0x1 0x2 0x3 0x4] [0x5 0x6 0x7 0x8 0x9] [0xa 0xb 0xc 0xd 0xe] [0xf 0x0 0x1 0x2 0x3] [0x4 0x5 0x6 0x7 0x8] ] """ raise ValueError("You must specify a modulus when creating a GF2E.")
cdef unsigned long _nrows, _ncols cdef unsigned long i, j
else:
def __cinit__(self, modulus=None, nrows=0, ncols=0, v=None): #################### WARNING ################### ## Before creating a GF2E, you must create a ## ## GF2EContext, and restore it. In Python, ## ## the error checking in __init__ will prevent## ## you from constructing an ntl_GF2E ## ## inappropriately. However, from Cython, you## ## could do r = ntl_GF2E.__new__(ntl_GF2E) without ## first restoring a GF2EContext, 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). ## ################################################ else: self.c = <ntl_GF2EContext_class>ntl_GF2EContext(modulus) self.c.restore_c()
cdef ntl_GF2E _new_element(self): cdef ntl_GF2E r
cdef ntl_mat_GF2E _new(self): cdef ntl_mat_GF2E r
def modulus_context(self): """ Returns the structure that holds the underlying NTL GF2E modulus.
EXAMPLES::
sage: ntl.GF2XHexOutput(0) sage: ctx = ntl.GF2EContext( ntl.GF2X([1,1,0,1,1,0,0,0,1]) ) sage: a = ntl.GF2E(ntl.ZZ_pX([1,1,3],2), ctx) sage: A= ntl.mat_GF2E(ctx, 1, 1, [a]) sage: cty = A.modulus_context(); cty NTL modulus [1 1 0 1 1 0 0 0 1] sage: ctx == cty True """
def __reduce__(self): """ EXAMPLES::
sage: k.<a> = GF(2^4) sage: ctx = ntl.GF2EContext(k) sage: A = ntl.mat_GF2E(ctx, 5,5, [0..24]) sage: A == loads(dumps(A)) True """
def __repr__(self): """ Return the string representation of self.
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: ntl.GF2XHexOutput(1) sage: ntl.mat_GF2E(ctx, 2,2,range(4)).__repr__() '[[0x0 0x1]\n[0x0 0x1]\n]' sage: ntl.GF2XHexOutput(0) sage: ntl.mat_GF2E(ctx, 2,2,range(4)).__repr__() '[[[] [1]]\n[[] [1]]\n]' """
def __mul__(ntl_mat_GF2E self, other): """ EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: ntl.GF2XHexOutput(1) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ntl.mat_GF2E(ctx, 5,5,[3..27]) sage: m*n ## indirect doctest [[0x87 0x04 0xc4 0xc7 0x87] [0x32 0x84 0x17 0x63 0x73] [0xa1 0x46 0x25 0xcd 0x2f] [0x1 0xcf 0xfb 0xd6 0x62] [0xcf 0x02 0x06 0xfd 0x79] ] """ other = ntl_mat_GF2E(other, self.c) raise ValueError("You can not perform arithmetic with matrices over different fields.")
def __sub__(ntl_mat_GF2E self, other): """ EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ntl.mat_GF2E(ctx, 5,5,[3..27]) sage: ntl.GF2XHexOutput(0) sage: m-n ## indirect doctest [[[1 1] [1 0 1] [1 1 1] [1 0 1] [1 1]] [[1 0 1 1] [1 1 1 1] [1 0 1 1] [1 1] [1 0 1]] [[1 1 1] [1 0 1] [1 1] [1 0 1 1 1] [1 1 1 1 1]] [[1 0 1 1 1] [1 1] [1 0 1] [1 1 1] [1 0 1]] [[1 1] [1 0 1 1] [1 1 1 1] [1 0 1 1] [1 1]] ] """ other = ntl_mat_GF2E(other, self.c) raise ValueError("You can not perform arithmetic with matrices over different fields.")
def __add__(ntl_mat_GF2E self, other): """ EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ntl.mat_GF2E(ctx, 5,5,[3..27]) sage: m+n ## indirect doctest [[[1 1] [1 0 1] [1 1 1] [1 0 1] [1 1]] [[1 0 1 1] [1 1 1 1] [1 0 1 1] [1 1] [1 0 1]] [[1 1 1] [1 0 1] [1 1] [1 0 1 1 1] [1 1 1 1 1]] [[1 0 1 1 1] [1 1] [1 0 1] [1 1 1] [1 0 1]] [[1 1] [1 0 1 1] [1 1 1 1] [1 0 1 1] [1 1]] ] """ other = ntl_mat_GF2E(other, self.c) raise ValueError("You can not perform arithmetic with matrices over different fields.")
def __neg__(ntl_mat_GF2E self): """ EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: -m == m ## indirect doctest True """
def __pow__(ntl_mat_GF2E self, long e, ignored): """ EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: m**2 == m*m ## indirect doctest True """
def __richcmp__(ntl_mat_GF2E self, other, int op): """ Compare self to other.
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ntl.mat_GF2E(ctx, 5,5,[3..27]) sage: m == n False sage: m == m True sage: m == [] False """
raise TypeError("matrices over GF(2^e) are not ordered")
cdef ntl_mat_GF2E b
def NumRows(self): """ Return the number of rows in self.
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) ; m.NumRows() 5 """
def NumCols(self): """ Return the number of columns in self.
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) ; m.NumCols() 5 """
def __setitem__(self, ij, x): """ EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: ntl.GF2XHexOutput(0) sage: m[0,0] [] sage: m[0,0] = 1 sage: m[0,0] [1] """ cdef int i, j
elif self.x.NumCols()==1 and (isinstance(ij, Integer) or isinstance(ij, int)): i = ij j = 0 elif self.x.NumRows()==1 and (isinstance(ij, Integer) or isinstance(ij, int)): i = 0 j = ij else: raise TypeError('ij is not a matrix index')
raise IndexError("array index out of range")
raise ValueError("You can not assign elements from different fields.")
def __getitem__(self, ij): """ EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: m[0,1] [1] sage: m[0,0] = 0 sage: m[0,0] [] """ cdef int i, j elif self.x.NumCols() == 1 and (isinstance(ij, Integer) or isinstance(ij, int)): i = ij j = 0 elif self.x.NumRows() == 1 and (isinstance(ij, Integer) or isinstance(ij, int)): i = 0 j = ij else: raise TypeError('ij is not a matrix index')
raise IndexError("array index out of range")
def determinant(self): """ Returns the determinant.
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: ntl.GF2XHexOutput(0) sage: ntl.mat_GF2E(ctx, 5,5,[0..24]).determinant() [0 1 0 1 1 1 1] sage: ntl.mat_GF2E(ctx, 5,5,[3..27]).determinant() [0 1 1 0 0 1] """
def gauss(self,ncols=-1): """ Performs unitary row operations so as to bring this matrix into row echelon form. If the optional argument \code{ncols} is supplied, stops when first ncols columns are in echelon form. The return value is the rank (or the rank of the first ncols columns).
INPUT:
- ``ncols`` - number of columns to process (default: all)
EXAMPLES::
sage: m = ctx = ntl.GF2EContext(ntl.GF2X([1,1,0,1,1,0,0,0,1])) sage: ntl.mat_GF2E(ctx, 5,5,[3..27]).gauss() 5 sage: ntl.mat_GF2E(ctx, 5,5).gauss() 0 sage: ntl.mat_GF2E(ctx, 5,5,[3..27]).gauss(3) 3 """
def list(self): """ Returns a list of the entries in this matrix
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 2,2,[ntl.GF2E_random(ctx) for x in range(2*2)]) sage: ntl.GF2XHexOutput(0) sage: m.list() [[1 1 0 0 1 0 1 1], [1 1 1 0 1 1 1], [0 1 1 1 1 0 0 1], [0 1 0 1 1 1]] """
def IsZero(self): """ Return True if self is zero, and false otherwise.
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ntl.mat_GF2E(ctx, 5,5) sage: m.IsZero() False sage: n.IsZero() True """ cdef long isZero
def _sage_(ntl_mat_GF2E self, k=None): """ Returns a ``Matrix`` over a ``FiniteField`` representation of this element.
INPUT:
- ``k`` - optional GF(2**deg)
OUTPUT: Matrix over k
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1]) sage: m = ntl.mat_GF2E(ctx, 2,2,[3..6]) sage: ntl.GF2XHexOutput(0) sage: m [[[1 1] [0 0 1]] [[1 0 1] [0 1 1]] ] sage: m._sage_() [ a + 1 a^2] [a^2 + 1 a^2 + a] """
def transpose(ntl_mat_GF2E self): """ Returns the transposed matrix of self.
OUTPUT: transposed Matrix
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = m.transpose() sage: n == m False sage: n.transpose() == m True """
def __invert__(self): """ Return $X = A^{-1}$; an error is raised if A is singular.
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ~m sage: o = n*m sage: o.IsIdent() True """
def IsIdent(self, n = -1): """ test if A is the n x n identity matrix
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 5,5,[0..24]) sage: n = ~m sage: o = n*m sage: o.IsIdent() True """
def IsDiag(self, long n, ntl_GF2E d): """ Test if X is an n x n diagonal matrix with d on diagonal.
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 3,3,[[0,1],0,0, 0,[0,1],0, 0,0,[0,1]]) sage: m.IsDiag(2, ntl.GF2E([0,1],ctx)) False sage: m.IsDiag(3, ntl.GF2E([0,1],ctx)) True """
def image(self): """ The rows of X are computed as basis of A's row space. X is row echelon form.
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 3,3,[0..24]) sage: ntl.GF2XHexOutput(1) sage: m.image() [[0x3 0x4 0x5] [0x0 0x1 0x2] [0x0 0x0 0xc1] ] """
def kernel(self): """ Computes a basis for the kernel of the map ``x -> x*A``, where ``x`` is a row vector.
EXAMPLES::
sage: ctx = ntl.GF2EContext([1,1,0,1,1,0,0,0,1]) sage: m = ntl.mat_GF2E(ctx, 3,3,[0..24]) sage: ntl.GF2XHexOutput(1) sage: m.kernel() [] """
def randomize(self, density=1, nonzero=False): """ Randomize ``density`` proportion of the entries of this matrix, leaving the rest unchanged.
INPUT:
- ``density`` - float; proportion (roughly) to be considered for changes - ``nonzero`` - Bool (default: ``False``); whether the new entries are forced to be non-zero
EXAMPLES::
sage: k.<a> = GF(2^4) sage: ctx = ntl.GF2EContext(k) sage: ntl.GF2XHexOutput(1) sage: A = ntl.mat_GF2E(ctx, 100,100) sage: A.randomize() sage: len([e for e in A.list() if e!=0]) 9346
sage: A = ntl.mat_GF2E(ctx, 100,100) sage: A.randomize(nonzero=True) sage: len([e for e in A.list() if e!=0]) 10000
sage: A = ntl.mat_GF2E(ctx, 100,100) sage: A.randomize(nonzero=True, density=0.1) sage: len([e for e in A.list() if e!=0]) 994
""" cdef long i,j cdef GF2E_c tmp
return _density = 1.0
else: for i in xrange(self.x.NumRows()): for j in xrange(self.x.NumCols()): if rstate.c_rand_double() <= _density: tmp = GF2E_random() mat_GF2E_setitem(&self.x, i, j, &tmp) else: else: |