__Fermat's (Little) Theorem__

`p`prime, 0<`x`<`p`

Then`x`^{(p-1)}=1 (mod`p`)- Example: Compute
`x`^{n}(mod`N`)

2^{n}(mod 7) = {1,2,4,1,2,4,1}

3^{n}(mod 7) = {1,3,2,6,4,5,1}

2^{n}(mod 15) = {1,2,4,8,1,2,4,8,1}

5^{n}(mod 15) = {1,5,10,5,10,...}

7^{n}(mod 7) = {1,7,4,13,1,7,4,13} - Def: The (multiplicative)
__order__of`x`mod`N`is the minimum exponent`e`>0 such that`x`^{e}=1(mod`N`)

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 12^{10} (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:

```
12
```^{2}=6 (mod 23)

12^{4}=6^{2}=13 (mod 23)

12^{8}=13^{2}=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:

```
12
```^{10}=12^{(8+2)}

=12^{8}*12^{2}

=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 10_{10}=1010_{2}.) 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:

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 `b`^{n}
=`b`*`b`*...*`b`

Robert Campbell, campbell@math.umbc.edu

29 March, 1998