blm.h File Reference

Bilinear Maps on Matrices over GF(2). More...

#include <m4ri/m4ri.h>
#include "m4rie/gf2e.h"

Go to the source code of this file.

Data Structures
struct	blm_t
	Bilinear Maps on Matrices over GF(2). More...

Macros
#define	M4RIE_CRT_LEN   (M4RIE_MAX_DEGREE + 1)
	We consider at most polynomials of degree M4RIE_MAX_DEGREE in CRT.

Functions
static int	blm_cost_crt (const int p[M4RIE_CRT_LEN])
int *	crt_init (const deg_t f_len, const deg_t g_len)
blm_t *	blm_init_crt (const gf2e *ff, const deg_t f_ncols, const deg_t g_ncols, const int *p, int djb)
blm_t *	_blm_finish_polymult (const gf2e *ff, blm_t *f)
void	blm_free (blm_t *f)
blm_t *	_blm_djb_compile (blm_t *f)
	Compile DJB map for f. More...
void	_mzd_ptr_apply_blm_mzd (mzd_t **X, const mzd_t **A, const mzd_t **B, const blm_t *f)
	Apply f (stored as a matrix) on A and B, writing to X. More...
void	_mzd_ptr_apply_blm_djb (mzd_t **X, const mzd_t **A, const mzd_t **B, const blm_t *f)
	Apply f (stored as a DJB map) on A and B, writing to X. More...
static void	_mzd_ptr_apply_blm (mzd_t **X, const mzd_t **A, const mzd_t **B, const blm_t *f)
	Apply f on A and B, writing to X. More...

Variables
const int	costs [17]

Detailed Description

Bilinear Maps on Matrices over GF(2).

This is used to realise mzd_poly_t multiplication.

Author

Martin Albrecht marti.nosp@m.nral.nosp@m.brech.nosp@m.t@go.nosp@m.oglem.nosp@m.ail..nosp@m.com

Function Documentation

blm_t* _blm_djb_compile

(

blm_t *

f

)

Compile DJB map for f.

Parameters

f	Bilinear map

blm_t* _blm_finish_polymult	(	const gf2e *	ff,
		blm_t *	f
	)

Given F and G compute H.

Parameters

ff	finite field for modular reduction
f	Bilinear Map with F and G already computed.

static void _mzd_ptr_apply_blm ( mzd_t **  X, const mzd_t **  A, const mzd_t **  B, const blm_t *  f  )

inlinestatic

Apply f on A and B, writing to X.

Parameters

X	Array of matrices
A	Array of matrices
B	Array of matrices
f	Bilinear map

void _mzd_ptr_apply_blm_djb	(	mzd_t **	X,
		const mzd_t **	A,
		const mzd_t **	B,
		const blm_t *	f
	)

Apply f (stored as a DJB map) on A and B, writing to X.

Parameters

X	Array of matrices
A	Array of matrices
B	Array of matrices
f	Bilinear map

void _mzd_ptr_apply_blm_mzd	(	mzd_t **	X,
		const mzd_t **	A,
		const mzd_t **	B,
		const blm_t *	f
	)

Apply f (stored as a matrix) on A and B, writing to X.

Parameters

X	Array of matrices
A	Array of matrices
B	Array of matrices
f	Bilinear map

static int blm_cost_crt ( const int  p[M4RIE_CRT_LEN] )

inlinestatic

Return the multiplication cost of the multiplication scheme p

void blm_free

(

blm_t *

f

)

Free bilinear map f.

blm_t* blm_init_crt	(	const gf2e *	ff,
		const deg_t	f_ncols,
		const deg_t	g_ncols,
		const int *	p,
		int	djb
	)

Compute H, F, G such that vec(c) = H*(F*vec(a) x G*vec(b)) with poly(c) = poly(a)*poly(b), deg(poly(a)) = a_ncols -1, deg(poly(b)) = b_ncols -1 and "x" being pointwise multiplication

This is realised by a multi-modular computation modulo the primes up to degree deg (which may not be irreducible polynomials, but merely co-prime).

1) We construct maps F,G which combine modular reduction to degree d and the linear map required for multiplying modulo a polynomial of degree d.

1.1) We deal with (x+infinity)^omega first

1.2) We deal with regular polynomial which are co-prime

the minimal polynomial is a square

the minimal polynomial is a fourth power

the minimal polynomial is an eigth power

2) We solve for H as we know poly(c) and (F*vec(a) x G*vec(b)). We pick points poly(a) = x^v, poly(b) = x^w (hence: poly(c) = x^(v+w)).

3) We compile DJB maps if asked for.

int* crt_init	(	const deg_t	f_len,
		const deg_t	g_len
	)

Find a list of co-prime polynomials p_i such that deg(prod(p_i)) >= f_len*g_len-1.

We store the number of polynomials of degree d in p[d]. We store the degree w of (x-infinity)^w in p[0].

Variable Documentation

const int costs[17]

costs[i] = cost of multiplying two polynomials of length i over \(\mathbb{F}_2\).