c4e_bigint.h File Reference

(Version 554)

Multi precision arithmetic in $\mathbb{N}$. More...

#include "c4e_elements.h"
Include dependency graph for c4e_bigint.h:

Go to the source code of this file.

Functions

C4eElemCmp c4e_bigint_cmp (C4E_CONST C4eElement *a, C4E_CONST C4eElement *b)
 Compares two (may be denormalized) big numbers.
void c4e_bigint_add (C4E_CONST C4eElement *a, C4E_CONST C4eElement *b, C4eElement *c)
 Addition of two big numbers $ a,b\in\mathbb{N}$.
C4eSysBool c4e_bigint_sub (C4E_CONST C4eElement *a, C4E_CONST C4eElement *b, C4eElement *c)
 The function subtracts two big numbers $ a,b\in\mathbb{N}$.
C4eSysBool c4e_bigint_dec (C4E_CONST C4eElement *b, C4eElement *c)
 Decrements a big number $ b\in\mathbb{N}$ by 1.
void c4e_bigint_mul (C4E_CONST C4eElement *C4E_RESTRICT a, C4E_CONST C4eElement *C4E_RESTRICT b, C4eElement *C4E_RESTRICT c)
 Multiplication of two big numbers $ a,b\in\mathbb{N} $ using the classical school book method.
void c4e_bigint_sqr (C4E_CONST C4eElement *C4E_RESTRICT b, C4eElement *C4E_RESTRICT c)
 Square of a big number $ b\in\mathbb{N} $.
void c4e_bigint_div (C4eElement *C4E_RESTRICT a, C4eElement *C4E_RESTRICT b, C4eElement *C4E_RESTRICT q)
 Division of two big numbers $ a,b\in\mathbb{N} $ using the Pope and Stein algorithm.
void c4e_bigint_mod (C4eElement *C4E_RESTRICT a, C4eElement *C4E_RESTRICT b)
 Modulo division of two big numbers $ a,b\in\mathbb{N} $ using the Pope and Stein algorithm.
void c4e_bigint_gcd (C4eElemTriple *a, C4eElemTriple *b, C4eArchSize n)
 Greatest Common Divisor of two numbers $ a,b\in\mathbb{N} $. It calculates the GCD of a->x and b->x together with the Bezout cofactors $ \alpha $ and $ \beta $ in equation $ \gcd(a,b)=2^{-n}(\pm\alpha a \mp\beta b) $.

Detailed Description

Multi precision arithmetic in $\mathbb{N}$.

Author:
Copyright (C) 2007-2015 Ralf Hoppe <ralf.hoppe@ieee.org>
Version:
Id
c4e_bigint.h 554 2015-03-09 16:50:11Z ralf

Definition in file c4e_bigint.h.

Function Documentation

C4eElemCmp c4e_bigint_cmp ( C4E_CONST C4eElement *  a,
C4E_CONST C4eElement *  b 
)

Compares two (may be denormalized) big numbers.

Parameters:
[in] a First number.
[in] b Second number.
Returns:
The function returns:
Return values:
C4eElemCmpGT if a is greater than b;
C4eElemCmpLT if a is less than b;
C4eElemCmpEQ if a is equal to b.
void c4e_bigint_add ( C4E_CONST C4eElement *  a,
C4E_CONST C4eElement *  b,
C4eElement *  c 
)

Addition of two big numbers $ a,b\in\mathbb{N}$.

Note:
The parameters a and b have not to be normalized. But if they are normalized the result c is normalized too.
Precondition:
c->digits must point to pre-allocated memory space for at least max (a->size, b->size) + 1 digits.
Parameters:
[in] a First summand.
[in] b Second summand.
[out] c Result of $ c=a+b $. It is allowed to set this argument pointing to a or b resp. c->digits pointing to a->digits or b->digits (accumulator mode).
C4eSysBool c4e_bigint_sub ( C4E_CONST C4eElement *  a,
C4E_CONST C4eElement *  b,
C4eElement *  c 
)

The function subtracts two big numbers $ a,b\in\mathbb{N}$.

Precondition:
c->digits must point to pre-allocated memory space for at least max (a->size, b->size) digits.
Postcondition:
The result c is normalized in case it's sign (the return value) is positive, else it is not normalized.
Parameters:
[in] a Minuend.
[in] b Subtrahend.
[out] c Result of $ c=a-b $, if negative in two's-complement representation. It is allowed to set this parameter pointing to a or b resp. c->digits pointing to a->digits or b->digits (accumulator mode).
Returns:
Sign of result
Return values:
C4E_FALSE if the result is positive
C4E_TRUE if the result is negative. In that case c is in two's-complement representation of size b->size.
See also:
C4eElement, C4E_ELEM_ASGN_MEM()
C4eSysBool c4e_bigint_dec ( C4E_CONST C4eElement *  b,
C4eElement *  c 
)

Decrements a big number $ b\in\mathbb{N}$ by 1.

Note:
If a negative result is indicated, the caller might add 1 to recover the original value.
Precondition:
c->digits must point to pre-allocated memory space for at least b->size digits.
Parameters:
[in] b The number to decrement.
[out] c Result $ c=b-1 $, which may alias b.
Returns:
Sign of result
Return values:
C4E_FALSE if the result is positive
C4E_TRUE if the result is negative. In that case c is in two's-complement representation, with the same size as b.
See also:
C4eElement, C4E_ELEM_ASGN_MEM()
void c4e_bigint_mul ( C4E_CONST C4eElement *C4E_RESTRICT  a,
C4E_CONST C4eElement *C4E_RESTRICT  b,
C4eElement *C4E_RESTRICT  c 
)

Multiplication of two big numbers $ a,b\in\mathbb{N} $ using the classical school book method.

Note:
If a and b are normalized then c is normalized too. In the other cases c is not normalized. If c is normalized, then the resulting size is a->size + b->size or a->size + b->size - 1.
Because this function implements the classical school book algorithm, it's complexity is O(a->size * b->size).
Precondition:
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.
c->digits must point to pre-allocated memory space for at least (a->size + b->size) digits.
Parameters:
[in] a First multiplier.
[in] b Second multiplier.
[out] c Result $ c=ab $.
See also:
C4eElement, C4E_ELEM_ASGN_MEM()
void c4e_bigint_sqr ( C4E_CONST C4eElement *C4E_RESTRICT  b,
C4eElement *C4E_RESTRICT  c 
)

Square of a big number $ b\in\mathbb{N} $.

Note:
This algorithm has complexity $ O(s^{2}/2) $ for large $ s $ (equivalent b->size).
The algorithm is derived directly from the school book multiplication method. With $ b=\sum_{i=0}^{n-1} b_i x^i $, where $ x $ is the radix, it is based on the following simplification:

\begin{align*} c &= b\sum_{i=0}^{n-1} b_i x^i = \sum_{i=0}^{n-1} b\; b_i x^i = \sum_{i=0}^{n-1} \sum_{k=0}^{n-1} b_k x^k b_i x^i = \sum_{i=0}^{n-1} \sum_{k=0}^{n-1} b_i b_k x^{i+k}\\ &= \sum_{i=0}^{n-1} \left(b_i^2 x^{2 i} + 2\sum_{k=0}^{i-1} b_i b_k x^{i+k} \right) = 2\sum_{i=0}^{n-1} \sum_{k=1}^{i-1} b_i b_k x^{i+k} + \sum_{i=0}^{n-1} b_i^2 x^{2 i} \end{align*}

Precondition:
Use of restrict qualifier indicates that aliasing b with c or aliasing b->digits with c->digits is not allowed.
c->digits must point to pre-allocated memory space for at least (2 * b->size) digits, at minimum one digit.
Parameters:
[in] b Argument to be squared.
[out] c Result $c=b^2$.
See also:
C4eElement, C4E_ELEM_ASGN_MEM()
void c4e_bigint_div ( C4eElement *C4E_RESTRICT  a,
C4eElement *C4E_RESTRICT  b,
C4eElement *C4E_RESTRICT  q 
)

Division of two big numbers $ a,b\in\mathbb{N} $ using the Pope and Stein algorithm.

div.jpg

Multi-Precision Division

Note:
The asymptotic complexity of the algorithm is O(a->size * b->size).
Attention:
Divisor b is temporary modified - so it must be writable. After function return it holds the same value as at function entry.
Precondition:
The numbers a and b must be normalized.
Divide by zero is not supported - catch this situation in advance (using macro C4E_ELEM_IS_ZERO(b)).
Use of restrict qualifier indicates that aliasing a with b or aliasing a->digits with b->digits is not allowed.
Because a->digits is also used as workplace, there must be pre-allocated memory space for at least (a->size + 1) digits.
q->digits must point to pre-allocated memory space for at least (a->size - b->size + 1) digits.
Bibliography:

D. A. Pope and M. L. Stein: Multiple Precision Arithmetic. CACM, 3:652-654, 1960

G. E. Collins and D. R. Musser: Analysis of the Pope- Stein Division Algorithm. University of Wisconsin Computer Sciences Department, Technical Report #55, Jan 1969

D. E. Knuth: The Art of Computer Programming, Vol. 2 (Semi-Numerical Algorithms). Addison-Wesley, 1997

Parameters:
[in,out] a Dividend as input, remainder $ r = a \bmod b$ as output.
[in] b Divisor (temporary modified).
[out] q Integer quotient q = floor(a / b). If q is NULL then no quotient will be returned.
See also:
C4eElement, C4E_ELEM_ASGN_MEM()
void c4e_bigint_mod ( C4eElement *C4E_RESTRICT  a,
C4eElement *C4E_RESTRICT  b 
)

Modulo division of two big numbers $ a,b\in\mathbb{N} $ using the Pope and Stein algorithm.

div.jpg

Multi-Precision Division

Note:
The asymptotic complexity of the algorithm is O(a->size * b->size).
Attention:
Divisor b is temporary modified - so it must be writable. After function return it holds the same value as at function entry.
Precondition:
The numbers a and b must be normalized.
Divide by zero is not supported - catch this situation in advance (using macro C4E_ELEM_IS_ZERO(b)).
Use of restrict qualifier indicates that aliasing a with b or aliasing a->digits with b->digits is not allowed.
Because a->digits is also used as workplace, there must be pre-allocated memory space for at least (a->size + 1) digits.
Bibliography:

D. A. Pope and M. L. Stein: Multiple Precision Arithmetic. CACM, 3:652-654, 1960

G. E. Collins and D. R. Musser: Analysis of the Pope- Stein Division Algorithm. University of Wisconsin Computer Sciences Department, Technical Report #55, Jan 1969

D. E. Knuth: The Art of Computer Programming, Vol. 2 (Semi-Numerical Algorithms). Addison-Wesley, 1997

Parameters:
[in,out] a Dividend as input, remainder $ r = a \bmod b$ as output.
[in] b Divisor (temporary modified).
See also:
C4eElement, C4E_ELEM_ASGN_MEM()
void c4e_bigint_gcd ( C4eElemTriple *  a,
C4eElemTriple *  b,
C4eArchSize  n 
)

Greatest Common Divisor of two numbers $ a,b\in\mathbb{N} $. It calculates the GCD of a->x and b->x together with the Bezout cofactors $ \alpha $ and $ \beta $ in equation $ \gcd(a,b)=2^{-n}(\pm\alpha a \mp\beta b) $.

Note:
If $ \gcd(a,b)=1 $ the algorithm computes $ \alpha = 2^n a^{-1} \pmod{b} $ in a->y and returns a->x in a->z, b->x in b->z, if n is zero.
If $ \gcd(a,b)=1 $ and for example also $ a=1 $ applies, then the Bezout cofactors will become (for this case): $ \alpha=1, \beta=0 $, independent of the value of $ b $.
The asymptotic complexity of the algorithm is O(a->x.size * b->x.size).
The coprime part a->z resp. b->z means: $\bar{a} = a/\gcd(a,b)$ resp. $\bar{b} = b/\gcd(a,b)$. With respect to Bezout's identity it satisfies the following equation:

\[\gcd(\bar{a},\bar{b}) = \alpha\bar{a} + \beta\bar{b} = 1 \]

means $\bar{a}$ and $\bar{b}$ are really coprime. Modular division of the identity above gives:

\begin{align*} \alpha\bar{a} &\equiv 1 \pmod{\bar{b}} \\ \beta\bar{b} &\equiv 1 \pmod{\bar{a}} \\ \end{align*}

Precondition:
The numbers a->x and b->x must be normalized, e.g. using function c4e_elem_norm().
It is not allowed that both numbers a->x and b->x are both zero (C4E_ELEM_IS_ZERO()).
The required digits space (in units of C4eArchDigit) for all big numbers is the maximum size of the two input values a->x and b->x plus (n / C4E_SYS_DIGIT_BITS + 1) digits.
Bibliography:

J. Stein: Computational problems associated with Racah algebra. Journal of Computational Physics, 1, 1967.

Bojanczyk, A. and R. P. Brent: A systolic algorithm for extended GCD computation. Computers & Mathematics with Applications, 14(4):233-238, 1987.

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

Parameters:
[in,out] a As an input parameter a->x holds the number, for which the GCD with b->x is calculated. As an output it returns:

  • zero in a->x;
  • Bezout cofactor $ \alpha $ in a->y;
  • the coprime part of a->x in a->z;
  • sign of cofactor in a->attr (0 if positive).
[in,out] b As an input parameter b->x holds the number, for which the GCD with a->x is calculated. As an output it returns:

  • the $ \gcd(a,b) $ in b->x;
  • Bezout cofactor $ \beta $ in b->y;
  • the coprime part of b->x in b->z;
  • sign of cofactor in b->attr (0 if positive).
[in] n The number n in equation $ \gcd(a,b)=2^{-n} (\pm\alpha a \mp\beta b) $. If n is zero it returns simply the Bezout cofactors in equation $ \gcd(a,b)= (\pm\alpha a \mp\beta b) $.
See also:
C4eElemTriple, c4e_elem_norm(), C4E_ELEM_IS_ZERO(), C4eElement, C4E_ELEM_ASGN_MEM()
Generated by Ralf Hoppe, Ginsterweg 49, 73230 Kirchheim unter Teck, Germany
on Sun Jun 7 14:10:50 2015 for CRY4E using doxygen 1.6.1