gfmatrix

package
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Jan 12, 2022 License: BSD-3-Clause Imports: 5 Imported by: 0

Documentation

Overview

Package gfmatrix implements basic operations on matrices over Rijndael's field and the random generation of new ones.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func GenerateRandom 

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

GenerateRandom generates a random invertible n-by-n matrix using the random source reader (for example, crypto/rand.Reader). Returns it and its inverse.

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 DeductiveMatrix 

type DeductiveMatrix struct {
	// contains filtered or unexported fields
}

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

func (dm *DeductiveMatrix) IsInDomain(x Row) bool

IsInDomain returns whether or not x is in the known span of A.

func (*DeductiveMatrix) IsInSpan 

func (dm *DeductiveMatrix) IsInSpan(y Row) bool

IsInSpan returns whether or not y is in the known span of A.

func (*DeductiveMatrix) Matrix 

func (dm *DeductiveMatrix) Matrix() Matrix

Matrix returns the deduced matrix.

func (*DeductiveMatrix) NovelInput 

func (dm *DeductiveMatrix) NovelInput() Row

NovelInput returns a random x not in the domain of A.

func (*DeductiveMatrix) NovelOutput 

func (dm *DeductiveMatrix) NovelOutput() Row

NovelOutput returns a random y not in the span of A.

type IncrementalMatrix 

type IncrementalMatrix struct {
	// contains filtered or unexported fields
}

IncrementalMatrix is an invertible matrix that can be generated incrementally. Implements sort.Interface.

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(16)

for !im.FullyDefined() {
	row := GenerateRandomRow(rand.Reader, 16)
	im.Add(row)
}

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 mutates nothing if the new row would make the matrix singular. 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) IsInSpan 

func (im *IncrementalMatrix) IsInSpan(in Row) bool

IsInSpan returns whether not not the given row can be expressed as a linear combination of currently known rows.

func (*IncrementalMatrix) Len 

func (im *IncrementalMatrix) Len() int

Len returns the number of linearly independent rows of the matrix. Part of an implementation of sort.Interface.

func (*IncrementalMatrix) Less 

func (im *IncrementalMatrix) Less(i, j int) bool

Less is part of an implementation of sort.Interface.

func (*IncrementalMatrix) Matrix 

func (im *IncrementalMatrix) Matrix() Matrix

Matrix returns the generated matrix.

func (*IncrementalMatrix) Novel 

func (im *IncrementalMatrix) Novel() Row

Novel returns a random row that is out of the span of the current matrix.

func (*IncrementalMatrix) Swap 

func (im *IncrementalMatrix) Swap(i, j int)

Swap is part of an implementation of sort.Interface.

type Matrix 

type Matrix []Row

Matrix represents a GF(2^8)-matrix.

func GenerateEmpty 

func GenerateEmpty(n, m int) Matrix

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

func GenerateIdentity 

func GenerateIdentity(n int) Matrix

GenerateIdentity generates the n-by-n identity matrix.

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 reader (for example, crypto/rand.Reader).

func (Matrix) Add 

func (e Matrix) Add(f Matrix) Matrix

Add adds two matrices from GF(2^8)^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 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) IsBinary 

func (e Matrix) IsBinary() bool

IsBinary returns true if the matrix contains only zero and one entries.

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

func (Matrix) Transpose 

func (e Matrix) Transpose() Matrix

Transpose returns the transpose of a matrix.

type Row 

type Row []number.ByteFieldElem

Row is a row / vector of elements from GF(2^8).

func GenerateRandomBinaryRow 

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

GenerateRandomBinaryRow generates a random n-component row containing only 1s and 0s, using the random source reader.

func GenerateRandomRow 

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

GenerateRandomRow generates a random n-component row using the random source reader.

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 two vectors from GF(2^8)^n.

func (Row) DotProduct 

func (e Row) DotProduct(f Row) number.ByteFieldElem

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

func (e Row) IsPermutation() bool

IsPermutation returns true if the row is a permutation of the first len(e) elements of GF(2^8) and false otherwise.

func (Row) IsZero 

func (e Row) IsZero() bool

IsZero returns whether or not the row is identically zero.

func (Row) OctaveString 

func (e Row) OctaveString() string

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

func (Row) ScalarMul 

func (e Row) ScalarMul(f number.ByteFieldElem) Row

ScalarMul multiplies a row by a scalar.

func (Row) Size 

func (e Row) Size() int

Size returns the dimension of the vector.

func (Row) String 

func (e Row) String() string

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.