# 7. Fermat & Euler's Theorem

## The Theorems

• Fermat's (Little) Theorem
p prime, 0<x<p
Then x(p-1)=1 (mod p)
• Example: Compute xn(mod N)
2n(mod 7) = {1,2,4,1,2,4,1}
3n(mod 7) = {1,3,2,6,4,5,1}
2n(mod 15) = {1,2,4,8,1,2,4,8,1}
5n(mod 15) = {1,5,10,5,10,...}
7n(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 xe=1(mod N)

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

## Factoring - Pollard p-1

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