Some Algorithms for Exponentiation: Trivial Algorithm

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Trivial Algorithm

A trivial algorithm is to sequentially compute a²,a³,…,a^b−1,a^b by multiplying an a^x term with a to obtain a^x+1. In the common-structure of last section, this means initializing x to 1 and increasing it by 1 in each iteration. As x is updated to x + 1, r can be updated to (modulo n):

ax+1 = axa = ra

The following method implements this algorithm:

typedef unsigned int uint;
typedef unsigned long ulong;

uint trivial(uint a, uint b, uint n)
{
  uint r, x;

  x = 1;
  r = a % n;

  /* loop-invariants:
       P: r = (a ^ x) % n */

  while(x != b)
  {
    x = x + 1;
    r = ((ulong)r * a) % n; /* maintain P */
  }
  /* x = b */

  return r;
}

This algorithm requires b− 1 multiplications, and so becomes ineﬃcient as b becomes larger.

[Prev] [Up] [Next]