c4e_gf2n.h File Reference

Polynomial arithmetic in finite field $\mathbb{F}_{2^n}$ . More...

#include "c4e_mod2n.h"

Include dependency graph for c4e_gf2n.h:

Defines
#define	C4E_GF2N_INV_SPACE(msize)
	Temp. space calculation (in units of C4eArchDigit) for function c4e_gf2n_inv().
Functions
void	c4e_gf2n_inv (C4E_CONST C4eElement C4E_RESTRICT a, C4E_CONST C4eElement C4E_RESTRICT b, C4E_CONST C4eElement C4E_RESTRICT m, C4eArchDigit tmp[], C4eElement C4E_RESTRICT c)
	Inversion of a field element in $\mathbb{F}_{2^n}$ , with multiplication by another element (so performing a division).
C4eSysStatus	c4e_gf2n_qsolve (C4E_CONST C4eElement C4E_RESTRICT m, C4E_CONST C4eElement C4E_RESTRICT beta, C4eArchDigit tmp[C4E_RESTRICT], C4eElement *C4E_RESTRICT z)
	Solves the quadratic equation $z^2 + z = \beta \bmod m(x)$ in $\mathbb{F}_{2^n}$ .

Detailed Description

Polynomial arithmetic in finite field $\mathbb{F}_{2^n}$ .

Definition in file c4e_gf2n.h.

#define C4E_GF2N_INV_SPACE ( msize )

Temp. space calculation (in units of C4eArchDigit) for function c4e_gf2n_inv().

Parameters:

[in] msize Size of binary polynomial m(x) in C4eArchDigit units.

Returns:: Required digit space (in units of C4eArchDigit) when using c4e_gf2n_inv() or functions based on it.

Definition at line 49 of file c4e_gf2n.h.

void c4e_gf2n_inv	(	C4E_CONST C4eElement *C4E_RESTRICT	a,
		C4E_CONST C4eElement *C4E_RESTRICT	b,
		C4E_CONST C4eElement *C4E_RESTRICT	m,
		C4eArchDigit	tmp[],
		C4eElement *C4E_RESTRICT	c
	)

Inversion of a field element in $\mathbb{F}_{2^n}$ , with multiplication by another element (so performing a division).

Precondition:: The polynomials a and m must be normalized (e.g. by using function c4e_elem_norm()) and must be unequal to zero.; The polynomials a and b must be reduced to m (e.g. by using c4e_poly_mod(), so having a size which is less/equal than the size of m).; tmp must point to pre-allocated memory space for at least (3U * C4E_GF2N_INV_SPACE(m->size)) digits.; Use of restrict qualifier indicates that aliasing a or b with c or aliasing a->digits or b->digits with c->digits is not allowed.

Bibliography:: Hankerson, Darrel, Alfred Menezes und Scott Vanstone: Guide to Elliptic Curve Cryptography. Springer, New York, 2004.

Bibliography:: Crandall, Richard und Carl Pomerance: Prime Numbers. A Computational Perspective. Springer, 2. Auflage, 2005.

Parameters:

`[in]`	a	Binary polynomial to be inverted modulo the polynomial `m`.
`[in]`	b	Binary polynomial to be multiplied with $a^{-1} \pmod m$ or NULL if only the element inversion is of interest (assumes `b` = 1).
`[in]`	m	Binary polynomial forming the modulus of the associated field $\mathbb{F}_{2^n}$ .
	tmp	Array of temporary space elements (see preconditions for details on size).
`[out]`	c	Binary polynomial which is $a^{-1}b \pmod m$ , normalized. If the result is zero then `a` seems not to be a valid field element ( $\gcd(a,m)=1$ does not hold true) and so does not have an inverse (error condition). The required C4eArchDigit digits space is C4E_GF2N_INV_SPACE(`m->size`).

See also:: c4e_elem_norm(), C4E_ELEM_IS_ZERO(), C4E_GF2N_INV_SPACE(), C4eElement, C4E_ELEM_ASGN_MEM()

C4eSysStatus c4e_gf2n_qsolve	(	C4E_CONST C4eElement *C4E_RESTRICT	m,
		C4E_CONST C4eElement *C4E_RESTRICT	beta,
		C4eArchDigit	tmp[C4E_RESTRICT],
		C4eElement *C4E_RESTRICT	z
	)

Solves the quadratic equation $z^2 + z = \beta \bmod m(x)$ in $\mathbb{F}_{2^n}$ .

Precondition:: tmp must point to pre-allocated memory space for at least (4U * m->size) digits.; The polynomial m must be normalized (e.g. by using function c4e_elem_norm()) and it must be unequal to zero. If m is not irreducible (which normally is a precondition for the existence of field $\mathbb{F}_{2^n}$ then this function may return error C4E_STATUS_EDOM.; The size of polynomial beta must be less/equal m->size (in best-case it is also reduced to m).; Use of restrict qualifier indicates that aliasing any of the argument pointers with the result pointer z is not allowed.

Bibliography:: Standard Specifications For Public-Key Cryptography. Std 1363-2000, IEEE, 2000.

Bibliography:: Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA). ANSI X9.62, 1998.

Parameters:

`[in]`	m	Binary polynomial forming the modulus of the associated field $\mathbb{F}_{2^n}$ .
`[in]`	beta	Right hand side of quadratic equation (value zero is allowed, then `z` becomes zero).
	tmp	Temporary used memory space of (4U * `m->size`) digits.
`[out]`	z	Result in equation $\beta = z^2(x) + z(x) \bmod m(x)$ , not normalized. The other solution then is $z \oplus 1$ . The required C4eArchDigit digits space for `z` is `m->size`.

Return values:

See also:: C4E_ELEM_IS_ZERO(), c4e_elem_norm(), C4eElement, C4E_ELEM_ASGN_MEM()