Team-Fly
Previous Section Next Section

14.1 Arithmetic

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).

Start Sidebar

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);

End Sidebar 
 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;
 }
Start Sidebar

Function:

Modular exponentiation

Syntax: 

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

Example:

a.mexp (e, m);

End Sidebar 
 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.

Start Sidebar

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;

End Sidebar
Start Sidebar

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;

End Sidebar
Start Sidebar

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;

End Sidebar
Start Sidebar

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;

End Sidebar
Start Sidebar

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;

End Sidebar
Start Sidebar

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;

End Sidebar
Start Sidebar

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 2e

Example:

a.mod 2(e); executes the operation a %= d;, where d = 2e

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.
End Sidebar
Start Sidebar

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)) // ...

End Sidebar
Start Sidebar

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);

End Sidebar
Start Sidebar

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);

End Sidebar
Start Sidebar

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);

End Sidebar
Start Sidebar

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);

End Sidebar
Start Sidebar

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);

End Sidebar
Start Sidebar

Function:

modular exponentiation

(2k-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);

End Sidebar
Start Sidebar

Function:

modular exponentiation

(25-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);

End Sidebar
Start Sidebar

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;

End Sidebar
Start Sidebar

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 ()) // ...

End Sidebar
Start Sidebar

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);

End Sidebar
Start Sidebar

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)) // ...

End Sidebar
Start Sidebar

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);

End Sidebar
Start Sidebar

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

End Sidebar
Team-Fly Previous Section Next Section