M4RIE  0.20120415
 All Data Structures Files Functions Variables Defines
Functions
Multiplication

Functions

mzd_slice_t_mzd_slice_mul_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.
mzd_slice_t_mzd_slice_mul_karatsuba2 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
 \( C = A \cdot B \) over \(\mathbb{F}_{2^2}\) using 3 multiplications over \(\mathbb{F}_2\) and 2 temporary \(\mathbb{F}_2\) matrices..
mzd_slice_t_mzd_slice_mul_karatsuba3 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
 \( C = A \cdot B \) over \(\mathbb{F}_{2^3}\) using 6 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices..
mzd_slice_t_mzd_slice_mul_karatsuba4 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
 \( C = A \cdot B \) over \(\mathbb{F}_{2^4}\) using 9 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices..
mzd_slice_t_mzd_slice_mul_karatsuba5 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
 \( C = A \cdot B \) over \(\mathbb{F}_{2^5}\) using 13 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices..
mzd_slice_t_mzd_slice_mul_karatsuba6 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
 \( C = A \cdot B \) over \(\mathbb{F}_{2^6}\) using 17 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices.
mzd_slice_t_mzd_slice_mul_karatsuba7 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
 \( C = A \cdot B \) over \(\mathbb{F}_{2^7}\) using 22 multiplications over \(\mathbb{F}_2\) and 3 temporary \(\mathbb{F}_2\) matrices.
mzd_slice_t_mzd_slice_mul_karatsuba8 (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
 \( C = A \cdot B \) over \(\mathbb{F}_{2^8}\) using 27 multiplications over \(\mathbb{F}_2\) and 15 temporary \(\mathbb{F}_2\) matrices.
static mzd_slice_t_mzd_slice_mul_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\).
static mzd_slice_tmzd_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\).
static mzd_slice_tmzd_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\).
mzd_slice_tmzd_slice_mul_scalar (mzd_slice_t *C, const word a, const mzd_slice_t *B)
 \( C = a \cdot B \).
mzd_slice_tmzd_slice_addmul_scalar (mzd_slice_t *C, const word a, const mzd_slice_t *B)
 \( C += a \cdot B \).
static mzd_slice_tmzd_slice_mul (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
 \( C = A \cdot B \).
static mzd_slice_tmzd_slice_addmul (mzd_slice_t *C, const mzd_slice_t *A, const mzd_slice_t *B)
 \( C = C + A \cdot B \).
mzed_tmzed_mul (mzed_t *C, const mzed_t *A, const mzed_t *B)
 \( C = A \cdot B \).
mzed_tmzed_addmul (mzed_t *C, const mzed_t *A, const mzed_t *B)
 \( C = C + A \cdot B \).
mzed_t_mzed_mul (mzed_t *C, const mzed_t *A, const mzed_t *B)
 \( C = A \cdot B \).
mzed_t_mzed_addmul (mzed_t *C, const mzed_t *A, const mzed_t *B)
 \( C = C + A \cdot B \).
mzed_tmzed_addmul_naive (mzed_t *C, const mzed_t *A, const mzed_t *B)
 \( C = C + A \cdot B \) using naive cubic multiplication.
mzed_tmzed_mul_naive (mzed_t *C, const mzed_t *A, const mzed_t *B)
 \( C = A \cdot B \) using naive cubic multiplication.
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.
mzed_tmzed_mul_scalar (mzed_t *C, const word a, const mzed_t *B)
 \( C = a \cdot B \).
mzed_tmzed_mul_newton_john (mzed_t *C, const mzed_t *A, const mzed_t *B)
 \(C = A \cdot B\) using Newton-John tables.
mzed_tmzed_addmul_newton_john (mzed_t *C, const mzed_t *A, const mzed_t *B)
 \(C = C + A \cdot B\) using Newton-John tables.
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.
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.
mzed_tmzed_mul_strassen (mzed_t *C, const mzed_t *A, const mzed_t *B, int cutoff)
 \( C = A \cdot B \) using Strassen-Winograd.
mzed_tmzed_addmul_strassen (mzed_t *C, const mzed_t *A, const mzed_t *B, int cutoff)
 \( C = C + A \cdot B \) using Strassen-Winograd.
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.
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.
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.

Function Documentation

static mzd_slice_t* _mzd_slice_mul_karatsuba ( mzd_slice_t C,
const mzd_slice_t A,
const mzd_slice_t B 
) [inline, static]

\( 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:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput matrix B.
See also:
mzed_mul() mzd_slice_mul() mzd_slice_mul_karatsuba()

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

Parameters:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput matrix B.
See also:
_mzd_slice_mul_karatsuba()

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

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:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput matrix B.
See also:
_mzd_slice_mul_karatsuba()

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

Parameters:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput matrix B.
See also:
_mzd_slice_mul_karatsuba()

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

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:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput matrix B.
See also:
_mzd_slice_mul_karatsuba()

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

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:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput matrix B.
See also:
_mzd_slice_mul_karatsuba()

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

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:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput matrix B.
See also:
_mzd_slice_mul_karatsuba()

\( C = A \cdot B \) over \(\mathbb{F}_{2^8}\) using 27 multiplications over \(\mathbb{F}_2\) and 15 temporary \(\mathbb{F}_2\) matrices.

Parameters:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput matrix B.
See also:
_mzd_slice_mul_karatsuba()

8 + 7 temporaries

Todo:
reduce memory requirements by writing formula explicitly
mzd_slice_t* _mzd_slice_mul_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:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput matrix B.
mzed_t* _mzed_addmul ( mzed_t C,
const mzed_t A,
const mzed_t B 
)

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

Parameters:
CPreallocated product matrix.
AInput matrix A.
BInput 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:
CPreallocated product matrix.
AInput matrix A.
BInput matrix B.
cutoffCrossover 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:
CPreallocated product matrix.
AInput matrix A.
BInput 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:
CPreallocated product matrix.
AInput matrix A.
BInput 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:
CPreallocated product matrix.
AInput matrix A.
BInput 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:
CPreallocated product matrix.
AInput matrix A.
BInput 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:
CPreallocated product matrix.
AInput matrix A.
BInput matrix B.
cutoffCrossover 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:
CMatrix (ignored)
AMatrix
BMartix (ignored)
static mzd_slice_t* mzd_slice_addmul ( mzd_slice_t C,
const mzd_slice_t A,
const mzd_slice_t B 
) [inline, static]

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

Parameters:
CPreallocated return matrix.
AInput matrix A.
BInput matrix B.
See also:
_mzd_slice_mul_karatsuba()
static mzd_slice_t* mzd_slice_addmul_karatsuba ( mzd_slice_t C,
const mzd_slice_t A,
const mzd_slice_t B 
) [inline, static]

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

Parameters:
CPreallocated return matrix.
AInput matrix A.
BInput matrix B.
See also:
_mzd_slice_mul_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:
CPreallocated product matrix.
afinite field element.
BInput matrix B.
static mzd_slice_t* mzd_slice_mul ( mzd_slice_t C,
const mzd_slice_t A,
const mzd_slice_t B 
) [inline, static]

\( C = A \cdot B \).

Parameters:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput matrix B.
See also:
_mzd_slice_mul_karatsuba()
static mzd_slice_t* mzd_slice_mul_karatsuba ( mzd_slice_t C,
const mzd_slice_t A,
const mzd_slice_t B 
) [inline, static]

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

Parameters:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput matrix B.
See also:
_mzd_slice_mul_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:
CPreallocated product matrix or NULL.
afinite field element.
BInput matrix B.
mzed_t* mzed_addmul ( mzed_t C,
const mzed_t A,
const mzed_t B 
)

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

Parameters:
CPreallocated product matrix, may be NULL for automatic creation.
AInput matrix A.
BInput 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:
CPreallocated product matrix.
AInput matrix A.
BInput 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:
CPreallocated product matrix, may be NULL for automatic creation.
AInput matrix A.
BInput 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:
CPreallocated product matrix, may be NULL for allocation.
AInput matrix A.
BInput matrix B.
cutoffCrossover 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:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput 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:
CPreallocated product matrix, may be NULL for automatic creation.
AInput matrix A.
BInput 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:
CPreallocated return matrix, may be NULL for automatic creation.
AInput matrix A.
BInput 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:
CPreallocated product matrix or NULL.
afinite field element.
BInput 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:
CPreallocated product matrix, may be NULL for allocation.
AInput matrix A.
BInput matrix B.
cutoffCrossover to basecase dimension > 64 or 0 for heuristic choice