Multiplication

Functions
static mzd_poly_t *	_mzd_poly_addmul_naive (mzd_poly_t *C, const mzd_poly_t *A, const mzd_poly_t *B)
	C += A*B using naive polynomial multiplication. More...
static mzd_poly_t *	_mzd_poly_addmul_karatsubs_balanced (mzd_poly_t *C, const mzd_poly_t *A, const mzd_poly_t *B)
	C += A*B using Karatsuba multiplication on balanced inputs. More...
void	_mzd_ptr_addmul_karatsuba2 (const gf2e *ff, mzd_t **X, const mzd_t **A, const mzd_t **B)
	\( X += A \cdot B \) over \(\mathbb{F}_{2^2}\) using 3 multiplications over \(\mathbb{F}_2\) and 2 temporary \(\mathbb{F}_2\) matrices. More...
mzd_slice_t *	_mzd_slice_addmul_naive (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
	\( C = A \cdot B \) using quadratic polynomial multiplication with matrix coefficients. More...
static mzd_slice_t *	_mzd_slice_addmul_karatsuba (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
	\( C = C + A \cdot B \) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\). More...
static mzd_slice_t *	mzd_slice_mul_karatsuba (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
	\( C = A \cdot B \) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\). More...
static mzd_slice_t *	mzd_slice_addmul_karatsuba (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
	\( C = C + A \cdot B\) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\). More...
static mzd_slice_t *	_mzd_slice_mul_blm (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B, blm_t *f)
	\( C = A \cdot B \) using bilinear maps over matrices over \(\mathbb{F}_2\). More...
static mzd_slice_t *	mzd_slice_mul_blm (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B, blm_t *f)
	\( C = A \cdot B \) using bilinear maps over matrices over \(\mathbb{F}_2\). More...
static mzd_slice_t *	mzd_slice_addmul_blm (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B, blm_t *f)
	\( C = C + A \cdot B \) using bilinear maps over matrices over \(\mathbb{F}_2\). More...
mzd_slice_t *	mzd_slice_mul_scalar (mzd_slice_t *C, const word a, const mzd_slice_t *B)
	\( C = a \cdot B \). More...
mzd_slice_t *	mzd_slice_addmul_scalar (mzd_slice_t *C, const word a, const mzd_slice_t *B)
	\( C += a \cdot B \). More...
static mzd_slice_t *	mzd_slice_mul (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
	\( C = A \cdot B \). More...
static mzd_slice_t *	mzd_slice_addmul (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
	\( C = C + A \cdot B \). More...
mzed_t *	mzed_mul (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\( C = A \cdot B \). More...
mzed_t *	mzed_addmul (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\( C = C + A \cdot B \). More...
mzed_t *	_mzed_mul (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\( C = A \cdot B \). More...
mzed_t *	_mzed_addmul (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\( C = C + A \cdot B \). More...
mzed_t *	mzed_addmul_naive (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\( C = C + A \cdot B \) using naive cubic multiplication. More...
mzed_t *	mzed_mul_naive (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\( C = A \cdot B \) using naive cubic multiplication. More...
mzed_t *	_mzed_mul_naive (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\( C = C + A \cdot B \) using naive cubic multiplication. More...
mzed_t *	mzed_mul_scalar (mzed_t *C, const word a, const mzed_t *B)
	\( C = a \cdot B \). More...
mzed_t *	mzed_mul_newton_john (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\(C = A \cdot B\) using Newton-John tables. More...
mzed_t *	mzed_addmul_newton_john (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\(C = C + A \cdot B\) using Newton-John tables. More...
mzed_t *	_mzed_mul_newton_john0 (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\(C = C + A \cdot B\) using Newton-John tables. More...
mzed_t *	_mzed_mul_newton_john (mzed_t *C, const mzed_t *A, const mzed_t *B)
	\(C = C + A \cdot B\) using Newton-John tables. More...
mzed_t *	mzed_mul_strassen (mzed_t *C, const mzed_t *A, const mzed_t *B, int cutoff)
	\( C = A \cdot B \) using Strassen-Winograd. More...
mzed_t *	mzed_addmul_strassen (mzed_t *C, const mzed_t *A, const mzed_t *B, int cutoff)
	\( C = C + A \cdot B \) using Strassen-Winograd. More...
mzed_t *	_mzed_mul_strassen (mzed_t *C, const mzed_t *A, const mzed_t *B, int cutoff)
	\( C = A \cdot B \) using Strassen-Winograd. More...
mzed_t *	_mzed_addmul_strassen (mzed_t *C, const mzed_t *A, const mzed_t *B, int cutoff)
	\( C = A \cdot B \) using Strassen-Winograd. More...
rci_t	_mzed_strassen_cutoff (const mzed_t *C, const mzed_t *A, const mzed_t *B)
	Return heurstic choice for crossover parameter for Strassen-Winograd multiplication given A, B and C. More...

Detailed Description

Function Documentation

static mzd_poly_t* _mzd_poly_addmul_karatsubs_balanced ( mzd_poly_t *  C, const mzd_poly_t *  A, const mzd_poly_t *  B  )

inlinestatic

C += A*B using Karatsuba multiplication on balanced inputs.

Parameters

C	Target polynomial.
A	Source polynomial.
B	Source polynomial.

static mzd_poly_t* _mzd_poly_addmul_naive ( mzd_poly_t *  C, const mzd_poly_t *  A, const mzd_poly_t *  B  )

inlinestatic

C += A*B using naive polynomial multiplication.

Parameters

C	Target polynomial.
A	Source polynomial.
B	Source polynomial.

void _mzd_ptr_addmul_karatsuba2	(	const gf2e *	ff,
		mzd_t **	X,
		const mzd_t **	A,
		const mzd_t **	B
	)

\( X += A \cdot B \) over \(\mathbb{F}_{2^2}\) using 3 multiplications over \(\mathbb{F}_2\) and 2 temporary \(\mathbb{F}_2\) matrices.

karatsuba.c If no finite field is given, polynomial arithmetic with polynomials of degree 1 is performed. In this case, X is expected to have at least length 3. If a finite field is given, then C is expected to have at least length 2.

The formula was taken from Peter L. Montgomery. "Five, Six, and Seven-Term Karatsuba-Like Formulae" in IEEE TRANSACTIONS ON COMPUTERS, VOL. 54, NO. 3, MARCH 2005/

Parameters

ff	Finite Field, may be NULL for polynomial arithmetic.
X	Preallocated return matrix, of length >= 2 (ff != NULL) or >=3 (ff == NULL)
A	Input matrix A, preallocated of length >= 2.
B	Input matrix B, preallocated of length >= 2.

See also

_mzd_ptr_addmul_karatsuba()

static mzd_slice_t* _mzd_slice_addmul_karatsuba ( mzd_slice_t *  C, const mzd_slice_t *  A, const mzd_slice_t *  B  )

inlinestatic

\( C = C + A \cdot B \) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\).

This function reduces matrix multiplication over \(\mathbb{F}_{2^e}\) to matrix multiplication over \(\mathbb{F}_2\).

As an example consider \( \mathbb{F}_4 \). The minimal polynomial is \( x^2 + x + 1 \). The matrix A can be represented as A0*x + A1 and the matrix B can be represented as B0*x + B1. Their product C is

\[ A0 \cdot B0 \cdot x^2 + (A0 \cdot B1 + A1 \cdot B0) \cdot x + A1*B1. \]

Reduction modulo x^2 + x + 1 gives

\[ (A0 \cdot B0 + A0 \cdot B1 + A1 \cdot B0) \cdot x + A1 \cdot B1 + A0 \cdot B0. \]

This can be re-written as

\[ ((A0 + A1) \cdot (B0 + B1) + A1 \cdot B1) \cdot x + A1 \cdot B1 + A0 \cdot B0 \]

and thus this multiplication costs 3 matrix multiplications over \(\mathbb{F}_2\) and 4 matrix additions over \(\mathbb{F}_2\).

This technique was proposed in Tomas J. Boothby and Robert W. Bradshaw; Bitslicing and the Method of Four Russians Over Larger Finite Fields; 2009; http://arxiv.org/abs/0901.1413

Parameters

C	Preallocated return matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.

See also

mzed_mul() mzd_slice_mul() mzd_slice_addmul_karatsuba()

mzd_slice_t* _mzd_slice_addmul_naive	(	mzd_slice_t *	C,
		const mzd_slice_t *	A,
		const mzd_slice_t *	B
	)

\( C = A \cdot B \) using quadratic polynomial multiplication with matrix coefficients.

Parameters

C	Preallocated return matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.

static mzd_slice_t* _mzd_slice_mul_blm ( mzd_slice_t *  C, const mzd_slice_t *  A, const mzd_slice_t *  B, blm_t *  f  )

inlinestatic

\( C = A \cdot B \) using bilinear maps over matrices over \(\mathbb{F}_2\).

Parameters

C	Preallocated return matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.
f	Blinear map such that C == H*((F*A) x (G*B)), if NULL it will be created and destroyed

Note

Calling _mzd_slice_addmul_karatsuba will be more efficient

mzed_t* _mzed_addmul	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

\( C = C + A \cdot B \).

Parameters

C	Preallocated product matrix.
A	Input matrix A.
B	Input matrix B.

mzed_t* _mzed_addmul_strassen	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B,
		int	cutoff
	)

\( C = A \cdot B \) using Strassen-Winograd.

This function uses Strassen-Winograd multiplication (Bodrato variant) recursively until it reaches the cutoff, where it switches to Newton-John table based multiplication or naive multiplication.

Parameters

C	Preallocated product matrix.
A	Input matrix A.
B	Input matrix B.
cutoff	Crossover to basecase dimension > 64

Note

See Marco Bodrato; "A Strassen-like Matrix Multiplication Suited for Squaring and Highest Power Computation"; http://bodrato.it/papres/#CIVV2008 for reference on the used sequence of operations.

mzed_t* _mzed_mul	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

\( C = A \cdot B \).

Parameters

C	Preallocated product matrix.
A	Input matrix A.
B	Input matrix B.

mzed_t* _mzed_mul_naive	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

\( C = C + A \cdot B \) using naive cubic multiplication.

Parameters

C	Preallocated product matrix.
A	Input matrix A.
B	Input matrix B.

mzed_t* _mzed_mul_newton_john	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

\(C = C + A \cdot B\) using Newton-John tables.

This is an optimised implementation.

Parameters

C	Preallocated product matrix.
A	Input matrix A.
B	Input matrix B.

See also

mzed_mul()

mzed_t* _mzed_mul_newton_john0	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

\(C = C + A \cdot B\) using Newton-John tables.

This is a simple implementation for clarity of presentation. Do not call, it is slow.

Parameters

C	Preallocated product matrix.
A	Input matrix A.
B	Input matrix B.

See also

mzed_mul_newton_john() mzed_mul()

mzed_t* _mzed_mul_strassen	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B,
		int	cutoff
	)

\( C = A \cdot B \) using Strassen-Winograd.

This function uses Strassen-Winograd multiplication (Bodrato variant) recursively until it reaches the cutoff, where it switches to Newton-John table based multiplication or naive multiplication.

Parameters

C	Preallocated product matrix.
A	Input matrix A.
B	Input matrix B.
cutoff	Crossover to basecase dimension > 64

Note

See Marco Bodrato; "A Strassen-like Matrix Multiplication Suited for Squaring and Highest Power Computation"; http://bodrato.it/papres/#CIVV2008 for reference on the used sequence of operations.

rci_t _mzed_strassen_cutoff	(	const mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

Return heurstic choice for crossover parameter for Strassen-Winograd multiplication given A, B and C.

Parameters

C	Matrix (ignored)
A	Matrix
B	Martix (ignored)

static mzd_slice_t* mzd_slice_addmul ( mzd_slice_t *  C, const mzd_slice_t *  A, const mzd_slice_t *  B  )

inlinestatic

\( C = C + A \cdot B \).

Parameters

C	Preallocated return matrix.
A	Input matrix A.
B	Input matrix B.

See also

_mzd_slice_addmul_karatsuba(n)

static mzd_slice_t* mzd_slice_addmul_blm ( mzd_slice_t *  C, const mzd_slice_t *  A, const mzd_slice_t *  B, blm_t *  f  )

inlinestatic

\( C = C + A \cdot B \) using bilinear maps over matrices over \(\mathbb{F}_2\).

Parameters

C	Preallocated return matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.
f	Blinear map such that C == C + H*((F*A) x (G*B)), if NULL it will be created and destroyed

Note

Calling mzd_slice_addmul_karatsuba will be more efficient

static mzd_slice_t* mzd_slice_addmul_karatsuba ( mzd_slice_t *  C, const mzd_slice_t *  A, const mzd_slice_t *  B  )

inlinestatic

\( C = C + A \cdot B\) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\).

Parameters

C	Preallocated return matrix.
A	Input matrix A.
B	Input matrix B.

See also

_mzd_slice_addmul_karatsuba()

mzd_slice_t* mzd_slice_addmul_scalar	(	mzd_slice_t *	C,
		const word	a,
		const mzd_slice_t *	B
	)

\( C += a \cdot B \).

Parameters

C	Preallocated product matrix.
a	finite field element.
B	Input matrix B.

static mzd_slice_t* mzd_slice_mul ( mzd_slice_t *  C, const mzd_slice_t *  A, const mzd_slice_t *  B  )

inlinestatic

\( C = A \cdot B \).

Parameters

C	Preallocated return matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.

See also

_mzd_slice_addmul_karatsuba()

static mzd_slice_t* mzd_slice_mul_blm ( mzd_slice_t *  C, const mzd_slice_t *  A, const mzd_slice_t *  B, blm_t *  f  )

inlinestatic

\( C = A \cdot B \) using bilinear maps over matrices over \(\mathbb{F}_2\).

Parameters

C	Preallocated return matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.
f	Blinear map such that C == H*((F*A) x (G*B)), if NULL it will be created and destroyed

Note

Calling mzd_slice_mul_karatsuba will be more efficient

static mzd_slice_t* mzd_slice_mul_karatsuba ( mzd_slice_t *  C, const mzd_slice_t *  A, const mzd_slice_t *  B  )

inlinestatic

\( C = A \cdot B \) using Karatsuba multiplication of polynomials over matrices over \(\mathbb{F}_2\).

Parameters

C	Preallocated return matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.

See also

_mzd_slice_addmul_karatsuba()

mzd_slice_t* mzd_slice_mul_scalar	(	mzd_slice_t *	C,
		const word	a,
		const mzd_slice_t *	B
	)

\( C = a \cdot B \).

Parameters

C	Preallocated product matrix or NULL.
a	finite field element.
B	Input matrix B.

mzed_t* mzed_addmul	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

\( C = C + A \cdot B \).

Parameters

C	Preallocated product matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.

mzed_t* mzed_addmul_naive	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

\( C = C + A \cdot B \) using naive cubic multiplication.

Parameters

C	Preallocated product matrix.
A	Input matrix A.
B	Input matrix B.

Note

There is no reason to call this function except for checking the correctness of other algorithms. It is very slow.

mzed_t* mzed_addmul_newton_john	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

\(C = C + A \cdot B\) using Newton-John tables.

Parameters

C	Preallocated product matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.

See also

_mzed_mul_newton_john() mzed_mul()

mzed_t* mzed_addmul_strassen	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B,
		int	cutoff
	)

\( C = C + A \cdot B \) using Strassen-Winograd.

This function uses Strassen-Winograd multiplication (Bodrato variant) recursively until it reaches the cutoff, where it switches to Newton-John table based multiplication or naive multiplication.

Parameters

C	Preallocated product matrix, may be NULL for allocation.
A	Input matrix A.
B	Input matrix B.
cutoff	Crossover to basecase dimension > 64 or 0 for heuristic choice.

mzed_t* mzed_mul	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

\( C = A \cdot B \).

Parameters

C	Preallocated return matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.

mzed_t* mzed_mul_naive	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

\( C = A \cdot B \) using naive cubic multiplication.

Parameters

C	Preallocated product matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.

Note

There is no reason to call this function except for checking the correctness of other algorithms. It is very slow.

mzed_t* mzed_mul_newton_john	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B
	)

\(C = A \cdot B\) using Newton-John tables.

Parameters

C	Preallocated return matrix, may be NULL for automatic creation.
A	Input matrix A.
B	Input matrix B.

See also

mzed_mul _mzed_mul_newton_john0()

mzed_t* mzed_mul_scalar	(	mzed_t *	C,
		const word	a,
		const mzed_t *	B
	)

\( C = a \cdot B \).

Parameters

C	Preallocated product matrix or NULL.
a	finite field element.
B	Input matrix B.

The algorithm proceeds as follows:

0) If a direct approach would need less lookups we use that.

1) We generate a lookup table of 16-bit wide entries

2) We use that lookup table to do 4 lookups per word

mzed_t* mzed_mul_strassen	(	mzed_t *	C,
		const mzed_t *	A,
		const mzed_t *	B,
		int	cutoff
	)

\( C = A \cdot B \) using Strassen-Winograd.

This function uses Strassen-Winograd multiplication (Bodrato variant) recursively until it reaches the cutoff, where it switches to Newton-John table based multiplication or naive multiplication.

Parameters

C	Preallocated product matrix, may be NULL for allocation.
A	Input matrix A.
B	Input matrix B.
cutoff	Crossover to basecase dimension > 64 or 0 for heuristic choice