|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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\) .
|
|
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\) .
|
|
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\) .
|
|
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\) .
|
|
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\) .
|
|
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\) .
|
|
mzd_slice_t * | mzd_slice_mul_scalar (mzd_slice_t *C, const word a, const mzd_slice_t *B) |
| \( C = a \cdot B \).
|
|
mzd_slice_t * | mzd_slice_addmul_scalar (mzd_slice_t *C, const word a, const mzd_slice_t *B) |
| \( C += a \cdot B \).
|
|
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 \).
|
|
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 \).
|
|
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_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_t * | mzed_addmul_naive (mzed_t *C, const mzed_t *A, const mzed_t *B) |
| \( C = 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 = 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_t * | mzed_mul_scalar (mzed_t *C, const word a, const mzed_t *B) |
| \( C = a \cdot B \).
|
|
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.
|
|
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.
|
|
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_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 = 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.
|
|
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()
\( 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()