6.1 First Approaches

Team-Fly

The simplest approach to exponentiation consists in following the recursive rule defined above and multiplying the base a by itself e times. This requires e − 1 modular multiplications, and for our purposes that is simply too many.

A more efficient way of proceeding is demonstrated in the following examples, in which we consider the binary representation of the exponent:

Here raising the base to the fifteenth power requires only six multiplications, as opposed to fourteen in the first method. Half of these are squarings, which, as we know, require only about half as much CPU time as regular multiplications. Exponentiation to the sixteenth power is accomplished with only four squarings.

Algorithms for exponentiation of a^e modulo m that calculate with the binary representation of the exponent are in general much more favorable than the first approach, as we are about to see. But first we must observe that the intermediate results of many integer multiplications one after the other quickly occupy more storage space than can be supplied by all the computer memory in the world, for from p = a^b follows log p = b log a, and thus the number of digits of the exponentiated a^b is the product of the exponent and the number of digits of the base. However, if we carry out the calculation of a^e in a residue class ring , that is, by means of modular multiplication, then we avoid this problem. In fact, most applications require exponentiation modulo m, so we may as well focus our attention on this case.

Let e = (e_n−1e_n−2...e₀)₂ with e_n−1 > 0 be the binary representation of the exponent e. Then the following binary algorithm requires ⌊log₂ e⌋ = n modular squarings and δ(e) − 1 modular multiplications, where

is the number of ones in the binary representation of e. If we assume that each digit takes on the value 0 or 1 with equal probability, then we may conclude that δ(e) has the expected value δ(e) = n/2, and altogether we have ⌊log₂ e⌋ multiplications for the algorithm.

Binary algorithm for exponentiation of a^e modulo m

Set p ← and i ← n − 2.
Set p ← p² mod m.
If e_i = 1, set p ← p · a mod m.
Set i ← i − 1; if i ≥ 0, go to step 2.
Output p.

The following implementation of this algorithm gives good results already for small exponents, those that can be represented by the USHORT type.

Function:	mixed modular exponentiation with USHORT exponent
Syntax:	int umexp_l (CLINT bas_l, USHORT e, CLINT p_l, CLINT m_l);
Input:	bas_l (base) e (exponent) m_l (modulus)
Output:	p_l (power residue)
Return:	E_CLINT_OK if all ok E_CLINT_DBZ if division by 0

 int umexp_l (CLINT bas_l, USHORT e, CLINT p_l, CLINT m_l) {   CLINT tmp_l, tmpbas_l;   USHORT k = BASEDIV2;   int err = E_CLINT_OK;   if (EQZ_L (m_l))     {       return E_CLINT_DBZ;    /* division by zero */     }   if (EQONE_L (m_l))     {       SETZERO_L (p_l);    /* modulus = 1 ==> remainder = 0 */       return E_CLINT_OK;     }   if (e == 0)    /* exponent = 0 ==> remainder = 1 */     {       SETONE_L (p_l);       return E_CLINT_OK;     }   if (EQZ_L (bas_l))     {       SETZERO_L (p_l);       return E_CLINT_OK;     }   mod_l (bas_l, m_l, tmp_l);   cpy_l (tmpbas_l, tmp_l);

After various checks the position of the leading 1 of the exponent e is determined. Here the variable k is used to mask the individual binary digits of e. Then k is shifted one more place to the right, corresponding to setting i ← n − 2 in step 1 of the algorithm.

   while ((e & k) == 0)     {       k >>= 1;     }   k >>= 1;

For the remaining digits of e we run through steps 2 and 3. The mask k serves as loop counter, which we shift to the right one digit each time. We then multiply by the base reduced modulo m_l.

   while (k != 0)     {       msqr_l (tmp_l, tmp_l, m_l);       if (e & k)          {            mmul_l (tmp_l, tmpbas_l, tmp_l, m_l);          }       k >>= 1;     }   cpy_l (p_l, tmp_l);   return err; }

The binary algorithm for exponentiation offers particular advantages when it is used with small bases. If the base is of type USHORT, then all of the multiplications p ← pa mod m in step 3 of the binary algorithm are of the type CLINT * USHORT modulo CLINT, which makes possible a substantial increase in speed in comparison to other algorithms that in this case would also require the multiplication of two CLINT types. The squarings, to be sure, use CLINT objects, but here we are able to use the advantageous squaring function.

Thus in the following we shall implement the exponentiation function wmexp_l(), the dual to umexp_l(), which accepts a base of type USHORT. The masking out of bits of the exponent is a good preparatory exercise in view of the following "large" functions for exponentiation. The way of proceeding consists essentially in testing one after the other each digit e_i of the exponent against a variable b initialized to 1 in the highest-valued bit, and then shifting to the right and repeating the test until b is equal to 0.

The following function wmexp_l() offers for small bases and exponents up to 1000 bits, for example, a speed advantage of about ten percent over the universal procedures that we shall tackle later.

Function:	modular exponentiation of a USHORT base
Syntax:	int wmexp_l (USHORT bas, CLINT e_l, CLINT rest_l, CLINT m_l);
Input:	bas (base) e_l (exponent) m_l (modulus)
Output:	rest_l (remainder of bas^e_l mod m_l)
Return:	E_CLINT_OK if all is ok E_CLINT_DBZ if division by 0

 int wmexp_l (USHORT bas, CLINT e_l, CLINT rest_l, CLINT m_l) {   CLINT p_l, z_l;   USHORT k, b, w;   if (EQZ_L (m_l))     {       return E_CLINT_DBZ;    /* division by 0 */     }   if (EQONE_L (m_l))     {       SETZERO_L (rest_l);    /* modulus = 1 ==> remainder = 0 */       return E_CLINT_OK;     }   if (EQZ_L (e_l))     {       SETONE_L (rest_l);       return E_CLINT_OK;     }   if (0 == bas)     {       SETZERO_L (rest_l);       return E_CLINT_OK;     }   SETONE_L (p_l);   cpy_l (z_l, e_l);

Beginning with the highest-valued nonzero bit in the highest-valued word of the exponent z_l the bits of the exponent are processed, where always we have first a squaring and then, if applicable, a multiplication. The bits of the exponent are tested in the expression if ((w & b) > 0) by masking their value with a bitwise AND.

   b = 1 << ((ld_l (z_l) - 1) & (BITPERDGT - 1UL));   w = z_l[DIGITS_L (z_l)];   for (; b > 0; b >>= 1)     {       msqr_l (p_l, p_l, m_l);       if ((w & b) > 0)          {            ummul_l (p_l, bas, p_l, m_l);          }     }

Then follows the processing of the remaining digits of the exponent.

   for (k = DIGITS_L (z_l) - 1; k > 0; k--)     {       w = z_l[k];       for (b = BASEDIV2; b > 0; b >>= 1)          {            msqr_l (p_l, p_l, m_l);            if ((w & b) > 0)               {                 ummul_l (p_l, bas, p_l, m_l);               }          }     }   cpy_l (rest_l, p_l);   return E_CLINT_OK; }

Team-Fly