matrix

package
v0.0.0-...-2f25eea Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Oct 20, 2016 License: BSD-3-Clause Imports: 5 Imported by: 42

Documentation

Overview

Package matrix implements basic operations on matrices in GF(2) and the random generation of new ones.

Index

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

func IgnoreNoBytes(row, col int) bool

IgnoreNoBytes implements the ByteIgnore interface. It sets no blocks to be blacklisted.

func IgnoreNoRows

func IgnoreNoRows(row int) bool

IgnoreNoRows implements the RowIgnore interface. It sets no rows to be blacklisted.

func LessThan

func LessThan(i, j Row) bool

LessThan returns true if row i is "less than" row j. If you use sort a permutation matrix according to LessThan, you'll always get the identity matrix.

Types

type ByteIgnore

type ByteIgnore func(int, int) bool

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

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

func GenerateEmpty(n, m int) Matrix

GenerateEmpty generates the n-by-n matrix with all entries set to 0.

func GenerateFull

func GenerateFull(n, m int) Matrix

GenerateFull generates the n-by-n matrix with all entries set to 1.

func GenerateIdentity

func GenerateIdentity(n int) Matrix

GenerateIdentity generates the n-by-n identity matrix.

func GeneratePartialIdentity

func GeneratePartialIdentity(n int, ignore RowIgnore) Matrix

GeneratePartialIdentity generates the n-by-n identity matrix on some rows and leaves others zero (the rows where ignore(row) == true).

func GeneratePermutationMatrix

func GeneratePermutationMatrix(permutation []int) Matrix

GeneratePermutationMatrix generates an 8n-by-8n permutation matrix corresponding to a permutation of {0, ..., n-1}.

func GenerateRandom

func GenerateRandom(reader io.Reader, n int) Matrix

GenerateRandom generates a random invertible n-by-n matrix using the random source random (for example, crypto/rand.Reader).

func GenerateTrueRandom

func GenerateTrueRandom(reader io.Reader, n int) Matrix

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) Add

func (e Matrix) Add(f Matrix) Matrix

Add adds two binary matrices from GF(2)^nxm.

func (Matrix) Compose

func (e Matrix) Compose(f Matrix) Matrix

Compose returns the result of composing e with f.

func (Matrix) Dup

func (e Matrix) Dup() Matrix

Dup returns a duplicate of this matrix.

func (Matrix) Equals

func (e Matrix) Equals(f Matrix) bool

Equals returns true if two matrices are equal and false otherwise.

func (Matrix) FindPivot

func (e Matrix) FindPivot(row, col int) int

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) GoString

func (e Matrix) GoString() string

func (Matrix) Invert

func (e Matrix) Invert() (Matrix, bool)

Invert computes the multiplicative inverse of a matrix, if it exists.

func (Matrix) LeftStretch

func (e Matrix) LeftStretch() Matrix

LeftStretch returns the matrix of left matrix multiplication by the given matrix.

func (Matrix) Mul

func (e Matrix) Mul(f Row) Row

Mul right-multiplies a matrix by a row.

func (Matrix) NullSpace

func (e Matrix) NullSpace() (basis []Row)

NullSpace returns a basis for the matrix's nullspace.

func (Matrix) OctaveString

func (e Matrix) OctaveString() string

OctaveString converts the matrix into a string that can be imported into Octave.

func (Matrix) RightStretch

func (e Matrix) RightStretch() Matrix

RightStretch returns the matrix of right matrix multiplication by the given matrix.

func (Matrix) Size

func (e Matrix) Size() (int, int)

Size returns the dimensions of the matrix in (Rows, Columns) order.

func (Matrix) String

func (e Matrix) String() string

String converts the matrix to space-and-dot notation.

func (Matrix) Trace

func (e Matrix) Trace() (out byte)

Trace returns the trace (sum/parity of elements on the diagonal) of a matrix: 0x00 or 0x01.

func (Matrix) Transpose

func (e Matrix) Transpose() Matrix

Transpose returns the transpose of a matrix.

type Row

type Row []byte

A binary row / vector in GF(2)^n.

func GenerateRandomNonZeroRow

func GenerateRandomNonZeroRow(reader io.Reader, n int) Row

GenerateRandomNonZeroRow generates a random non-zero n-component row.

func GenerateRandomRow

func GenerateRandomRow(reader io.Reader, n int) Row

GenerateRandomRow generates a random n-component row.

func NewRow

func NewRow(n int) Row

NewRow returns an empty n-component row.

func (Row) Add

func (e Row) Add(f Row) Row

Add adds (XORs) two vectors.

func (Row) Cancels

func (e Row) Cancels(f Row) bool

Returns true if e should be used to cancel out a bit in f.

func (Row) DotProduct

func (e Row) DotProduct(f Row) bool

DotProduct computes the dot product of two vectors.

func (Row) Dup

func (e Row) Dup() Row

Dup returns a duplicate of this row.

func (Row) Equals

func (e Row) Equals(f Row) bool

Equals returns true if two rows are equal and false otherwise.

func (Row) GetBit

func (e Row) GetBit(i int) byte

GetBit returns the ith component of the vector: 0x00 or 0x01.

func (Row) Height

func (e Row) Height() int

Height returns the position of the first non-zero entry in the row, or -1 if the row is zero.

func (Row) IsZero

func (e Row) IsZero() bool

IsZero returns true if the row is identically zero.

func (Row) Mul

func (e Row) Mul(f Row) Row

Mul component-wise multiplies (ANDs) two vectors.

func (Row) OctaveString

func (e Row) OctaveString() string

OctaveString converts the row into a string that can be imported into Octave.

func (Row) SetBit

func (e Row) SetBit(i int, x bool)

SetBit sets the ith component of the vector to 0x01 is x = true and 0x00 if x = false.

func (Row) Size

func (e Row) Size() int

Size returns the dimension of the vector.

func (Row) String

func (e Row) String() string

String converts the row into space-and-dot notation.

func (Row) Weight

func (e Row) Weight() (w int)

Weight returns the hamming weight of this row.

type RowIgnore

type RowIgnore func(int) bool

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

func IgnoreRows(positions ...int) RowIgnore

IgnoreRows returns an impementation of the RowIgnore interface which is true at all given positions and false at all others.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL