14.1 Arithmetic

Team-Fly

The following member functions implement the fundamental arithmetic operations as well as modular operations for calculation in residue class rings over the integers as accumulator operations: The object to which a called function belongs contains the function result as implicit argument after its termination. Accumulator functions are efficient, since they operate to the greatest extent without internal auxiliary objects and thus save unnecessary assignments and calls to constructors.

For the cases in which a free assignment of the results of calculations is unavoidable, or in which the automatic overwriting of the implicit argument of the member functions with the result is not desired, the member functions were extended by means of like-named analogous friend functions together with additional friend functions. These are not discussed further here, but are recorded in Appendix B. The treatment of possible error situations in LINT functions that can arise from the use of CLINT functions will be discussed in full in Chapter 15.

Before we list the public member functions, we consider first as an example of their implementation the functions

   LINT& LINT::mexp (const LINT& e, const LINT& m );

and

   LINT& LINT::mexp (const USHORT e, const LINT& m);

for exponentiation, an operation for which C++, alas, offers no operator. The functions mexp() were constructed in such a way that the functions used are, according to the type of the operands, the C functions mexpk_l(), mexpkm_l(), umexp_l(), and umexpm_l(), optimized for this purpose (with the corresponding arithmetic friend functions we are likewise dealing with the exponentiation functions wmexp_l() and wmexpm_l() with USHORT base).

Function:	Modular exponentiation with automatic use of Montgomery exponentiation if the modulus is odd.
Syntax:	const LINT& LINT::mexp (const LINT& e, const LINT& m);
Input:	implicit argument (base) e (exponent) m (modulus)
Return:	pointer to the remainder
Example:	a.mexp (e, m);

  const LINT& LINT::mexp (const LINT& e, const LINT& m)  {    int error;    if (!init) panic (E_LINT_VAL, "mexp", 0, __LINE__);    if (!e.init) panic (E_LINT_VAL, "mexp", 1, __LINE__);    if (!m.init) panic (E_LINT_VAL, "mexp", 2, __LINE__);    err = mexp_l (n_l, e.n_l, n_l, m.n_l);    /* mexp_l() uses mexpk_l() or mexpkm_l() */    switch (error)      {         case 0:           status = E_LINT_OK;           break;         case E_CLINT_DBZ:           panic (E_LINT_DBZ, "mexp", 2, __LINE__);           break;         default:           panic (E_LINT_ERR, "mexp", error, __LINE__);      }    return *this;  }

Function:

Modular exponentiation

Syntax:

 const LINT& LINT::mexp (const USHORT e, const LINT& m);

Example:

a.mexp (e, m);

  const LINT& LINT::mexp (const USHORT e, const LINT& m)  {    int err;    if (!init) panic (E_LINT_VAL, "mexp", 0, __LINE__);    if (!m.init) panic (E_LINT_VAL, "mexp", 1, __LINE__);    err = umexp_l (n_l, e, n_l, m.n_l);    switch (err)      {         // Code as above with mexp (const LINT& e, const LINT& m)      }    return *this;  }

We now present a collection of additional arithmetic and number-theoretic member functions.

Function:	addition
Syntax:	const LINT& LINT::add(const LINT& s);
Input:	implicit argument (summand) s (summand)
Return:	pointer to the sum
Example:	a.add (s); executes the operation a += s;

Function:	subtraction
Syntax:	const LINT& LINT::sub (const LINT& s);
Input:	implicit argument (minuend) s (subtrahend)
Return:	pointer to the difference
Example:	a.sub (s); executes the operation a −= s;

Function:	multiplication
Syntax:	const LINT& LINT::mul (const LINT& s);
Input:	implicit argument (factor) s (factor)
Return:	pointer to the product
Example:	a.mul (s); executes the operation a *= s;

Function:	squaring
Syntax:	const LINT& LINT::sqr (void);
Input:	implicit argument (factor)
Return:	pointer to the implicit argument, which contains the square
Example:	a.sqr (); executes the operation a *= a;

Function:	division with remainder
Syntax:	const LINT& LINT::divr(const LINT& d, LINT& r);
Input:	implicit argument (dividend) d (divisor)
Output	r (remainder of the division modulo d)
Return:	pointer to the implicit argument, which contains the quotient
Example:	a.divr (d, r); executes the operation a /= d; r = a % d;

Function:	residue
Syntax:	const LINT& LINT::mod(const LINT& d);
Input:	implicit argument (dividend) d (divisor)
Return:	pointer to the implicit argument, which contains the remainder of the division modulo d
Example:	a.mod (d); executes the operation a %= d;

Function:	residue modulo a power of 2
Syntax:	const LINT& LINT::mod2 (const USHORT e)
Input:	implicit argument (dividend) ^e (exponent of the power of 2 divisor)
Return:	pointer to the implicit argument, which contains the remainder of the division modulo 2^e
Example:	a.mod 2(e); executes the operation a %= d;, where d = 2^e
Note:	mod2 cannot be created by overloading the previously presented function mod(), since mod() also accepts a USHORT argument, which is changed automatically into a LINT object by means of the appropriate constructor. Since it cannot be determined from the arguments which function is meant, mod2() is given its own name.

Function:	test for equality modulo m
Syntax:	const int LINT::mequ (const LINT& b, const LINT& m);
Input:	implicit argument a second argument b modulus m
Return:	1 if a ≡ b mod m, 0 otherwise
Example:	if (a.mequ (b, m)) // ...

Function:	modular addition
Syntax:	const LINT& LINT::madd(const LINT& s, const LINT& m);
Input:	implicit argument (summand) s (summand) m (modulus)
Return:	pointer to the implicit argument, which contains the sum modulo m
Example:	a.madd (s, m);

Function:	modular subtraction
Syntax:	const LINT& LINT::msub(const LINT& s, const LINT& m);
Input:	implicit argument (minuend) s (subtrahend) m (modulus)
Return:	pointer to the implicit argument, which contains the difference modulo m
Example:	a.msub (s, m);

Function:	modular multiplication
Syntax:	const LINT& LINT::mmul (const LINT& s, const LINT& m);
Input:	implicit argument (factor) s (factor) m (modulus)
Return:	pointer to the implicit argument, which contains the product modulo m
Example:	a.mmul (s, m);

Function:	modular squaring
Syntax:	const LINT& LINT::msqr (const LINT& m);
Input:	implicit argument (factor) m (modulus)
Return:	pointer to the implicit argument, which contains the square modulo m
Example:	a.msqr (m);

Function:	modular exponentiation with exponent a power of 2
Syntax:	const LINT& LINT::mexp2 (const USHORT e, const LINT& m);
Input:	implicit argument (base) e (power to which 2 is to be raised) m (modulus)
Return:	pointer to the implicit argument, which contains the power modulo m
Example:	a.mexp2 (e, m);

Function:	modular exponentiation (2^k-ary method, Montgomery reduction)
Syntax:	const LINT& LINT::mexpkm (const LINT& e, const LINT& m);
Input:	implicit argument (base) e (exponent) m (odd modulus)
Return:	pointer to the implicit argument, which contains the power modulo m
Example:	a.mexpkm (e, m);

Function:	modular exponentiation (2⁵-ary method, Montgomery reduction)
Syntax:	const LINT& LINT::mexp5m(const LINT& e, const LINT& m);
Input:	implicit argument (base) e (exponent) m (odd modulus)
Return:	pointer to the implicit argument, which contains the power modulo m
Example:	a.mexp5m (e, m);

Function:	left/right shift
Syntax:	const LINT& LINT::shift (const int noofbits);
Input:	implicit argument (multiplicand/dividend) (+/−) noofbits (number of bit positions to be shifted)
Return:	pointer to the implicit argument, which contains the result of the shift operation
Example:	a.shift (512); executes the operation a <<= 512;

Function:	test for divisibility by 2 of a LINT object
Syntax:	const int LINT::iseven (void);
Input:	test candidate a as implicit argument
Return:	1 if a is odd, 0 otherwise
Example:	if(a.iseven ()) // ...

Function:	set a binary digit of a LINT object to 1
Syntax:	const LINT& LINT::setbit (const unsigned int pos);
Input:	implicit argument a position pos of the bit to be set (counted from 0)
Return:	pointer to a with the set bit at position pos
Example:	a.setbit (512);

Function:	test a binary digit of a LINT object
Syntax:	const int LINT::testbit (const unsigned int pos);
Input:	implicit argument a position pos of the bit to be tested (counted from 0)
Return:	1 if the bit at position pos is set, 0 otherwise
Example:	if(a.testbit (512)) // ...

Function:	set a binary digit of a LINT object to 0
Syntax:	const LINT& LINT::clearbit (const unsigned int pos);
Input:	implicit argument a position pos of the bit to be cleared (counted from 0)
Return:	pointer to a with the cleared bit at position pos
Example:	a.clearbit (512);

Function:	exchange values of two LINT objects
Syntax:	const LINT& LINT::fswap (LINT& b);
Input:	implicit argument a position b (the value to be swapped for a)
Return:	pointer to the implicit argument with the value b
Example:	a.fswap (b); exchanges the values a and b

Team-Fly