c4e_mod2n.h File Reference

(Version 551)

Modular (polynomial) arithmetic in ring $\mathbb{Z}_2[x] / m(x)$ . More...

#include "c4e_poly.h"

Include dependency graph for c4e_mod2n.h:

Functions
void	c4e_mod2n_sqr (C4E_CONST C4eElement C4E_RESTRICT a, C4E_CONST C4eElement C4E_RESTRICT m, C4eElement *C4E_RESTRICT c)
	Square of a binary polynomial (having coefficients from $\mathbb{F}_2$ ), with modular reduction.
void	c4e_mod2n_pow (C4E_CONST C4eElement C4E_RESTRICT a, C4E_CONST C4eElement C4E_RESTRICT n, C4E_CONST C4eElement C4E_RESTRICT m, C4eElement C4E_RESTRICT tmp, C4eElement *c)
	Modulo-power $c(x)=a^{n}(x) \bmod m(x)$ of a binary polynomial (with coefficients in $\mathbb{F}_{2}$ ).

Detailed Description

Modular (polynomial) arithmetic in ring $\mathbb{Z}_2[x] / m(x)$ .

Note:: This interface is the counterpart to c4e_modn.h.

Author:: Copyright (C) 2013, 2015 Ralf Hoppe <ralf.hoppe@ieee.org>

Version:

Id: c4e_mod2n.h 551 2015-03-01 12:37:45Z ralf

Definition in file c4e_mod2n.h.

Function Documentation

void c4e_mod2n_sqr	(	C4E_CONST C4eElement *C4E_RESTRICT	a,
		C4E_CONST C4eElement *C4E_RESTRICT	m,
		C4eElement *C4E_RESTRICT	c
	)

Square of a binary polynomial (having coefficients from $\mathbb{F}_2$ ), with modular reduction.

Note:: The algorithm has complexity O(a->size ^ 2).

Precondition:: The size of argument a MUST be less/equal m->size, but not to be normalized (except for performance reasons).; c->digits must point to pre-allocated memory space for at least m->size digits.; Use of restrict qualifier indicates that aliasing a with c or aliasing a->digits with c->digits is not allowed.

Parameters:

`[in]`	a	Polynomial to be squared.
`[in]`	m	Modulus (binary polynomial), unequal to zero.
`[out]`	c	Result $c(x)=a^2(x) \bmod m(x)$ , not normalized.

See also:: C4eElement, C4E_ELEM_ASGN_MEM()

void c4e_mod2n_pow	(	C4E_CONST C4eElement *C4E_RESTRICT	a,
		C4E_CONST C4eElement *C4E_RESTRICT	n,
		C4E_CONST C4eElement *C4E_RESTRICT	m,
		C4eElement *C4E_RESTRICT	tmp,
		C4eElement *	c
	)

Modulo-power $c(x)=a^{n}(x) \bmod m(x)$ of a binary polynomial (with coefficients in $\mathbb{F}_{2}$ ).

The algebraic operation performed by this left-to-right algorithm is a (modular) exponentiation in finite field $\mathbb{F}_2^{\deg m}$ . It is based on the binary representation of exponent $n = n_k 2^k + n_{k-1} 2^{k-1} + \dots + n_1 2 + n_0$ , which results in:

$\begin{align*} c(x) = a^{n}(x) &= a^{n_k 2^k}(x)\cdot a^{n_{k-1}2^{k-1}}(x)\cdots a^{n_1 2}(x)\cdot a^{n_0}(x)\\ &= ((\cdots((a^2(x))^{n_k}\cdot a^{n_{k-1}}(x))^2\cdots a^{n_2}(x))^2\cdot a^{n_1}(x))^2\cdot a^{n_0}(x) \end{align*}$

Note:: The parameters a and n should be normalized, because of performance reasons.; Parameter a should be reduced to m on function entry, for example using c4e_poly_mod(a_in, NULL, m, a_out).

Precondition:: It is not allowed that both a(x) and n are zero. The caller has to ensure this, may be using macro C4E_ELEM_IS_ZERO().; c->digits and tmp->digits must point to pre-allocated memory space for at least m->size digits.; The parameter m must be normalized, for example using function c4e_elem_norm().; Use of restrict qualifier indicates that aliasing any of the argument pointers with the result pointer is not allowed.

Parameters:

`[in]`	a	Argument (binary polynomial).
`[in]`	n	Big number exponent.
`[in]`	m	Modulus (binary polynomial), unequal to zero.
	tmp	Temporary space needed for intermediate results.
`[out]`	c	Result $c(x) = a^{n}(x) \bmod m(x)$ , not normalized.

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

c4e_mod2n.h File Reference

(Version 551)

Functions

Detailed Description

Function Documentation