Documentation
¶
Overview ¶
Package matrix implements basic operations on matrices in GF(2) and the random generation of new ones.
Index ¶
- func GenerateRandomPartial(reader io.Reader, n int, ignore ByteIgnore, idIgnore RowIgnore) (Matrix, Matrix)
- func IgnoreNoBytes(row, col int) bool
- func IgnoreNoRows(row int) bool
- func LessThan(i, j Row) bool
- type ByteIgnore
- type DeductiveMatrix
- type IncrementalMatrix
- func (im *IncrementalMatrix) Add(raw Row) bool
- func (im *IncrementalMatrix) Dup() IncrementalMatrix
- func (im *IncrementalMatrix) FullyDefined() bool
- func (im *IncrementalMatrix) Inverse() Matrix
- func (im *IncrementalMatrix) IsIn(in Row) bool
- func (im *IncrementalMatrix) Len() int
- func (im *IncrementalMatrix) Less(i, j int) bool
- func (im *IncrementalMatrix) Matrix() Matrix
- func (im *IncrementalMatrix) NovelRow(n int) Row
- func (im *IncrementalMatrix) NovelSize() int
- func (im *IncrementalMatrix) Row(n int) Row
- func (im *IncrementalMatrix) Size() int
- func (im *IncrementalMatrix) Swap(i, j int)
- type Matrix
- func GenerateEmpty(n, m int) Matrix
- func GenerateFull(n, m int) Matrix
- func GenerateIdentity(n int) Matrix
- func GeneratePartialIdentity(n int, ignore RowIgnore) Matrix
- func GeneratePermutationMatrix(permutation []int) Matrix
- func GenerateRandom(reader io.Reader, n int) Matrix
- func GenerateTrueRandom(reader io.Reader, n int) Matrix
- func (e Matrix) Add(f Matrix) Matrix
- func (e Matrix) Compose(f Matrix) Matrix
- func (e Matrix) Dup() Matrix
- func (e Matrix) Equals(f Matrix) bool
- func (e Matrix) FindPivot(row, col int) int
- func (e Matrix) GoString() string
- func (e Matrix) Invert() (Matrix, bool)
- func (e Matrix) LeftStretch() Matrix
- func (e Matrix) Mul(f Row) Row
- func (e Matrix) NullSpace() (basis []Row)
- func (e Matrix) OctaveString() string
- func (e Matrix) RightStretch() Matrix
- func (e Matrix) Size() (int, int)
- func (e Matrix) String() string
- func (e Matrix) Trace() (out byte)
- func (e Matrix) Transpose() Matrix
- type Row
- func (e Row) Add(f Row) Row
- func (e Row) Cancels(f Row) bool
- func (e Row) DotProduct(f Row) bool
- func (e Row) Dup() Row
- func (e Row) Equals(f Row) bool
- func (e Row) GetBit(i int) byte
- func (e Row) Height() int
- func (e Row) IsZero() bool
- func (e Row) Mul(f Row) Row
- func (e Row) OctaveString() string
- func (e Row) SetBit(i int, x bool)
- func (e Row) Size() int
- func (e Row) String() string
- func (e Row) Weight() (w int)
- type RowIgnore
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func GenerateRandomPartial ¶
func GenerateRandomPartial(reader io.Reader, n int, ignore ByteIgnore, idIgnore RowIgnore) (Matrix, Matrix)
GenerateRandomPartial generates an invertible n-by-n matrix which is random in some locations and the identity / zero in others, using the random source random (for example, crypto/rand.Reader). idIgnore is passes to GeneratePartialIdentity--it sets which rows of the identity are zero. The generated matrix is filled with random data everywhere that ignore(row, col) == false.
func IgnoreNoBytes ¶
IgnoreNoBytes implements the ByteIgnore interface. It sets no blocks to be blacklisted.
func IgnoreNoRows ¶
IgnoreNoRows implements the RowIgnore interface. It sets no rows to be blacklisted.
Types ¶
type ByteIgnore ¶
ByteIgnore blacklists blocks of a matrix from an operation; rows and columns are handeled at the byte-level, not the bit-level. It's used by GenerateRandomPartial to control where a matrix is random and fixed.
func IgnoreBytes ¶
func IgnoreBytes(positions ...int) ByteIgnore
IgnoreBytes returns an implementation of the ByteIgnore interface which is true if the row OR column equals a given position and false otherwise.
type DeductiveMatrix ¶
type DeductiveMatrix struct {
Input, Output IncrementalMatrix
}
DeductiveMatrix is a generalization of IncrementalMatrix that allows the incremental deduction of matrices.
Like incremental matrices, its primary use-case is in cryptanalyses and search algorithms, where we can do some work to obtain an (input, output) pair that we believe defines a matrix. We don't want to do more work than necessary and we also can't just obtain n (input, output) pairs because of linear dependence, etc.
func NewDeductiveMatrix ¶
func NewDeductiveMatrix(n int) *DeductiveMatrix
NewDeductiveMatrix returns a new n-by-n deductive matrix.
func (*DeductiveMatrix) Assert ¶
func (dm *DeductiveMatrix) Assert(in, out Row) (learned bool)
Assert represents an assertion that A(in) = out. The function will panic if this is inconsistent with previous assertions. It it's not, it returns whether or not the assertion contained new information about A.
func (*DeductiveMatrix) Dup ¶
func (dm *DeductiveMatrix) Dup() *DeductiveMatrix
Dup returns a duplicate of dm.
func (*DeductiveMatrix) FullyDefined ¶
func (dm *DeductiveMatrix) FullyDefined() bool
FullyDefined returns true if the assertions made give a fully defined matrix.
func (*DeductiveMatrix) Inverse ¶
func (dm *DeductiveMatrix) Inverse() Matrix
Inverse returns the deduced matrix's inverse.
func (*DeductiveMatrix) Matrix ¶
func (dm *DeductiveMatrix) Matrix() Matrix
Matrix returns the deduced matrix.
type IncrementalMatrix ¶
type IncrementalMatrix struct {
// contains filtered or unexported fields
}
IncrementalMatrix is an invertible matrix that can be generated incrementally. It implements sort.Interface (but don't worry about that).
For example, in cryptanalyses, we might be able to do some work and discover some rows of a matrix. We want to stop working as soon as its fully defined, but we also can't just work until we have n rows because we might have recovered duplicate or linearly dependent rows.
Example ¶
im := NewIncrementalMatrix(128)
for !im.FullyDefined() {
im.Add(GenerateRandomRow(rand.Reader, 128))
}
fmt.Println(im.Matrix())
Output:
func NewIncrementalMatrix ¶
func NewIncrementalMatrix(n int) IncrementalMatrix
NewIncrementalMatrix initializes a new n-by-n incremental matrix.
func (*IncrementalMatrix) Add ¶
func (im *IncrementalMatrix) Add(raw Row) bool
Add tries to add the row to the matrix. It fails if the new row is linearly dependent with another row. Add returns success or failure.
func (*IncrementalMatrix) Dup ¶
func (im *IncrementalMatrix) Dup() IncrementalMatrix
Dup returns a duplicate of im.
func (*IncrementalMatrix) FullyDefined ¶
func (im *IncrementalMatrix) FullyDefined() bool
FullyDefined returns true if the matrix has been fully defined and false if it hasn't.
func (*IncrementalMatrix) Inverse ¶
func (im *IncrementalMatrix) Inverse() Matrix
Inverse returns the generated matrix's inverse.
func (*IncrementalMatrix) IsIn ¶
func (im *IncrementalMatrix) IsIn(in Row) bool
IsIn returns whether or not the given row can be expressed as a linear combination of known rows.
func (*IncrementalMatrix) Len ¶
func (im *IncrementalMatrix) Len() int
func (*IncrementalMatrix) Less ¶
func (im *IncrementalMatrix) Less(i, j int) bool
func (*IncrementalMatrix) Matrix ¶
func (im *IncrementalMatrix) Matrix() Matrix
Matrix returns the generated matrix.
func (*IncrementalMatrix) NovelRow ¶
func (im *IncrementalMatrix) NovelRow(n int) Row
NovelRow returns the nth row that is NOT a linear combination of the known rows of the matrix. n will be considered modulo im.NovelSize().
func (*IncrementalMatrix) NovelSize ¶
func (im *IncrementalMatrix) NovelSize() int
NovelSize returns the number of rows that are NOT a linear combination of the known rows of the matrix..
func (*IncrementalMatrix) Row ¶
func (im *IncrementalMatrix) Row(n int) Row
Row returns the nth row that is a linear combination of the known rows of the matrix. n will be considered modulo im.Size().
func (*IncrementalMatrix) Size ¶
func (im *IncrementalMatrix) Size() int
Size returns the number of rows that can be expressed as a linear combination of the known rows of the matrix.
func (*IncrementalMatrix) Swap ¶
func (im *IncrementalMatrix) Swap(i, j int)
type Matrix ¶
type Matrix []Row
Matrix is a logical, or (0, 1)-matrix
func GenerateEmpty ¶
GenerateEmpty generates the n-by-n matrix with all entries set to 0.
func GenerateFull ¶
GenerateFull generates the n-by-n matrix with all entries set to 1.
func GenerateIdentity ¶
GenerateIdentity generates the n-by-n identity matrix.
func GeneratePartialIdentity ¶
GeneratePartialIdentity generates the n-by-n identity matrix on some rows and leaves others zero (the rows where ignore(row) == true).
func GeneratePermutationMatrix ¶
GeneratePermutationMatrix generates an 8n-by-8n permutation matrix corresponding to a permutation of {0, ..., n-1}.
func GenerateRandom ¶
GenerateRandom generates a random invertible n-by-n matrix using the random source random (for example, crypto/rand.Reader).
func GenerateTrueRandom ¶
GenerateTrueRandom generates a random n-by-n matrix (not guaranteed to be invertible) using the random source random (for example, crypto/rand.Reader).
func (Matrix) FindPivot ¶
FindPivot finds a row with non-zero entry in column col, starting at the given row and moving down. It returns the index of the given row or -1 if one does not exist.
func (Matrix) LeftStretch ¶
LeftStretch returns the matrix of left matrix multiplication by the given matrix.
func (Matrix) OctaveString ¶
OctaveString converts the matrix into a string that can be imported into Octave.
func (Matrix) RightStretch ¶
RightStretch returns the matrix of right matrix multiplication by the given matrix.
type Row ¶
type Row []byte
A binary row / vector in GF(2)^n.
func GenerateRandomNonZeroRow ¶
GenerateRandomNonZeroRow generates a random non-zero n-component row.
func GenerateRandomRow ¶
GenerateRandomRow generates a random n-component row.
func (Row) DotProduct ¶
DotProduct computes the dot product of two vectors.
func (Row) Height ¶
Height returns the position of the first non-zero entry in the row, or -1 if the row is zero.
func (Row) OctaveString ¶
OctaveString converts the row into a string that can be imported into Octave.
func (Row) SetBit ¶
SetBit sets the ith component of the vector to 0x01 is x = true and 0x00 if x = false.
type RowIgnore ¶
RowIgnore blacklists rows of a matrix from an operation; rows are handeled at the byte-level, not the bit-level. It's used by GeneratePartialIdentity and GeneratePartialRandom to leave empty rows in a matrix.
func IgnoreRows ¶
IgnoreRows returns an impementation of the RowIgnore interface which is true at all given positions and false at all others.
Source Files