c4e_modn.h File Reference

(Version 579)

Modular arithmetic in ring $\mathbb{Z}_m$ . More...

#include "c4e_bigint.h"

Include dependency graph for c4e_modn.h:

Defines
#define	C4E_MODN_POW_SPACE(msize)
	Size calculation macro for modular exponentiation parameters size (in units of C4eArchDigit).
Functions
void	c4e_modn_pow (C4eElement C4E_RESTRICT a, C4E_CONST C4eElement C4E_RESTRICT n, C4eElement C4E_RESTRICT m, C4eElement C4E_RESTRICT tmp, C4eElement *c)
	Power in $\mathbb{Z}_m$ , means $c=a^n \bmod m$ .
void	c4e_modn_crt (C4eElemTriple C4E_RESTRICT p, C4eElemTriple C4E_RESTRICT q)
	Chinese Remainder Theorem (CRT).

Detailed Description

Modular arithmetic in ring $\mathbb{Z}_m$ .

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

Version:

Id: c4e_modn.h 579 2015-05-24 18:00:40Z ralf

Definition in file c4e_modn.h.

Define Documentation

#define C4E_MODN_POW_SPACE ( msize )

Size calculation macro for modular exponentiation parameters size (in units of C4eArchDigit).

Parameters:

[in] msize Size of modulus in units of C4eArchDigit.

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

Definition at line 47 of file c4e_modn.h.

Function Documentation

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

Power $ c=a^n $ in $\mathbb{Z}_m$ , means $c=a^n \bmod m$ .

The implemented left-to-right algorithm 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 gives:

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

Note:: If modulus m is odd, it uses Montgomery's algorithm.; This algorithm has an asymptotic complexity of about , if also designates the size of modulus m.

Attention:: The modulus m is temporary modified - so it must be writable. After function return it holds the same values as at function entry.

Precondition:: It is not allowed that both numbers a and n are zero. The caller has to ensure this, may be using macro C4E_ELEM_IS_ZERO().; The required digits space (in units of C4eArchDigit) for a is (m->size + 1). The space for tmp->digits and c->digits is C4E_MODN_POW_SPACE(m->size), but only if m is odd (Montgomery algorithm). In case m is even, the required digits space for tmp->digits and c->digits is (2U * m->size) digits.; The parameters m and a must be normalized, for example using function c4e_elem_norm().; Parameter a must be reduced to m on entry. Use for example function c4e_bigint_mod() to ensure this.

Bibliography:: Montgomery, P.: Modular multiplication without trial division. Mathematics of Computation, 44(170):519-521, 1985.

Bibliography:: Koc, Cetin Kaya, Tolga Acar and Burton S. Kaliski, Jr.: Analyzing and Comparing Montgomery Multiplication Algorithms. IEEE Micro, 16(3):26-33, Juni 1996.

Bibliography:: Burton S. Kaliski: The Montgomery Inverse and Its Applications IEEE Transactions on Computers, 44(8):1064-1065, August 1995.

Parameters:

`[in]`	a	Big number `a` in $c=a^n \bmod m$ . Notice that number `a` is destroyed.
`[in]`	n	Exponent `n` in $c=a^n \bmod m$ .
`[in]`	m	Modulus (greater than zero), temporary modified.
	tmp	Temporary space needed for intermediate results.
`[out]`	c	Result `c` in $c=a^n \bmod m$ , normalized.

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

void c4e_modn_crt	(	C4eElemTriple *C4E_RESTRICT	p,
		C4eElemTriple *C4E_RESTRICT	q
	)

Chinese Remainder Theorem (CRT).

The Chinese Remainder Theorem can be used to solve linear congruences of the form:

$\begin{align*} y &\equiv a \pmod{p} \\ y &\equiv b \pmod{q} \end{align*}$

under the precondition that p and q are coprime ( $\gcd(p,q) = 1$ ). Typically the CRT is given in the literature by the following formula:

$y = \alpha b p + \beta a q + kpq, \qquad k \in \mathbb{Z}$

which is closely related to the extended GCD algorithm and Bezout's theorem: $\gcd(p,q) = \alpha p + \beta q = 1$ . The implemented algorithm uses a variant introduced by H.L. Garner:

$\begin{align*} y &= a + \alpha p (b-a) + kpq, \qquad k \in \mathbb{Z} \\ y &= a + p [\alpha (b-a) \bmod q], \qquad 0 \leq y < pq \end{align*}$

Notice that in this form the Bezout cofactor $\beta$ is not needed - so q->y is used (internally) for intermediate calculations.

Bibliography:: Koc, Cetin Kaya: High-Speed RSA Implementation. Technical Report TR-201, RSA Laboratories, 1994. Version 2.0

Bibliography:: Garner, Harvey L.: The Residue Number System. IRE Transactions on Electronic Computers, 8(2):140-147, Juni 1959.

Note:: Internally, if the result of is negative the algorithm adds once to the result, which so becomes positive. Therefore result is always positive and less than . In consequence the members p->attr and q->attr have no meaning as return parameters.

Precondition:

Numbers p->x resp. q->x must be less than the associated modulus p->z resp. q->z.

All input parameters referenced via p and q, that are big numbers must be normalized, for example using function c4e_elem_norm().

The caller hast to ensure that numbers p->z and q->z are relatively prime, else the algorithm does produce a wrong result.

The caller must provide at least the following digits space (each digit of size C4E_ARCH_DIGIT_SIZE):

p->z.size + q->z.size + 1 for p->x and q->x;
2 * q->z.size for q->x, if that is greater than p->z.size + q->z.size + 1;
p->x.size for q->y.

Parameters:

[in,out]

p

Input parameters of first (modular) congruence $y &\equiv a \pmod{p}$ resp. first summand in Bezout's theorem $\alpha p + \beta q = 1$ and return value $ y $

:

modulus in p->z (unchanged);
cofactor $\alpha$ in p->y (unchanged);
sign of cofactor $\alpha$ in p->attr;
number in p->x. At function return member p->x holds the (positive) result .