7. Fermat & Euler's Theorem

Number Theory, Math 413, Fall 1998


The Theorems

Computation - Exponentiation via the Russian Peasant Algorithm

When computing a power of a number with a finite modulus there are efficient ways to do it and inefficient ways to do it. In this section we will outline a commonly used efficient method which has the curious name "the Russian Peasant algorithm".

The most obvious way to compute 1210 (mod 23) is to multiply 12 a total of nine times, reducing the result mod 23 at each step. A more efficient method which takes only four multiplications is accomplished by first noting that:

122=6 (mod 23)
124=62=13 (mod 23)
128=132=8 (mod 23)

We have now performed three squarings and, by noting that the exponent breaks into powers of 2 as 10=8+2, we can rewrite our computation:

1210=12(8+2)
=128*122
=8*6=2(mod 23)

So our algorithm consists of writing the exponent as powers of two. (This can be done by writing it as a number base 2 and reading off successive digits - eg 1010=10102.) Now we multiply successive squares of the base number for each digit of the exponent which is a "1".

The following short JavaScript program implements this algorithm:

function powMod(base,exp,modulus)
{
   var accum=1, i=0, basepow2=base;
   // Look at each bit of exp, low to high
   while ((exp>>i)>0)
   {
      // If the exponent bit of exp is 1 multiply by base^(2^i)
      if(((exp>>i) & 1) == 1)
      {
         accum = (accum*basepow2) % modulus;
      };
      // In any event compute base^(2^i) for next i value
      basepow2 = (basepow2*basepow2) % modulus;
      i = i+1;
   };
   return accum;
}
    

And examples can be computed here:

^ (mod ) =

We note that this algorithm is applicable to not just the modular integers, but any computation of the form a+a+...+a (n times, where n is an integer and where the operation "+" is any group operation). This computation is commonly denoted na, even if you are in a group where no operation "*" is defined. Supposedly the algorithm originated as a way an uneducated peasant, who could add but not multiply, could multiply two numbers. We have illustrated it as an efficient way to compute bn =b*b*...*b, but it is an efficient way to compute powers in any finite field.

Application - RSA Encryption

Primitive Elements

Prime Testing - 2-Pseudoprimes

Factoring - Pollard p-1

Robert Campbell, campbell@math.umbc.edu
29 March, 1998