NOTE: This site is obsolete. See book draft (in PDF):

The Laws of Cryptography with Java Code.

---

Fermat's Theorem.

Recall that Fermat's theorem says that given a prime p and a non-zero number a, a^p-1 mod p is always equal to 1. Here is a table for p = 11 illustrating this theorem. Notice below that the value is always 1 by the time the power gets to 10, but sometimes the value gets to 1 earlier. The initial run up to the 1 value is shown in red boldface in the table. A value of a for which the whole row is red is called a generator. In this case 2, 6, 7, and 8 are generators.

Values pa for p = 11, a < 11
p	a		a1	a2	a3	a4	a5	a6	a7	a8	a9	a10
11	2		2	4	8	5	10	9	7	3	6	1
11	3		3	9	5	4	1	3	9	5	4	1
11	4		4	5	9	3	1	4	5	9	3	1
11	5		5	3	4	9	1	5	3	4	9	1
11	6		6	3	7	9	10	5	8	4	2	1
11	7		7	5	2	3	10	4	6	9	8	1
11	8		8	9	6	4	10	3	2	5	7	1
11	9		9	4	3	5	1	9	4	3	5	1
11	10		10	1	10	1	10	1	10	1	10	1

---

Java code to produce the table above and the one below.

// Fermat.java: given a prime integer p, calculate powers of a
//   fixed element a mod p.  Output html table
public class Fermat {

   // main function to do all the work
   public static void main (String[] args) {
      long p = (Long.parseLong(args[0])); // the fixed prime base
      System.out.println("<table border nosave >");
      System.out.println("<tr><th>p</th><th>a</th><th></th>");
      for (int col = 1; col < p; col++)
         System.out.print("<th>a<sup>" + col + "</sup></th>");
      System.out.println("</tr><tr colspan=" + (p+2) + "></tr>");
      for (long row = 2; row < p; row++) {
         System.out.print("<tr align=right><td>" + p);
         System.out.print("</td><td>" + row + "</td><td></td>");
         boolean firstCycle = true;
         for (long col = 1; col < p; col++) {
            if (firstCycle)
               System.out.print("<td><b><font color=FF0000>" +
                  pow(row, col, p) + "</font></b></td>");
            else
               System.out.print("<td>"    + pow(row, col, p) + "</td>");
            if (firstCycle)
               if (pow(row, col, p) == 1) firstCycle = false;
         }
         System.out.println("</tr>");
      }
      System.out.println("</table>");
   } // end of main

   // pow: calculate x^y mod p, without overflowing
   //    (Algorithm adapted from Gries, The Science of Programming, p. 240
   public static long pow(long x, long y, long p) {
      long z = 1;
      while (y > 0) {
         while (y%2 == 0) {
            x = (x*x) % p;
            y = y/2;
         }
         z = (z*x) % p;
         y = y - 1;
      }
      return z;
   }
} 

---

Here is a larger table with p = 23. There are 10 generators.

Values pa for p = 23, a < 23
p	a		a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12	a13	a14	a15	a16	a17	a18	a19	a20	a21	a22
23	2		2	4	8	16	9	18	13	3	6	12	1	2	4	8	16	9	18	13	3	6	12	1
23	3		3	9	4	12	13	16	2	6	18	8	1	3	9	4	12	13	16	2	6	18	8	1
23	4		4	16	18	3	12	2	8	9	13	6	1	4	16	18	3	12	2	8	9	13	6	1
23	5		5	2	10	4	20	8	17	16	11	9	22	18	21	13	19	3	15	6	7	12	14	1
23	6		6	13	9	8	2	12	3	18	16	4	1	6	13	9	8	2	12	3	18	16	4	1
23	7		7	3	21	9	17	4	5	12	15	13	22	16	20	2	14	6	19	18	11	8	10	1
23	8		8	18	6	2	16	13	12	4	9	3	1	8	18	6	2	16	13	12	4	9	3	1
23	9		9	12	16	6	8	3	4	13	2	18	1	9	12	16	6	8	3	4	13	2	18	1
23	10		10	8	11	18	19	6	14	2	20	16	22	13	15	12	5	4	17	9	21	3	7	1
23	11		11	6	20	13	5	9	7	8	19	2	22	12	17	3	10	18	14	16	15	4	21	1
23	12		12	6	3	13	18	9	16	8	4	2	1	12	6	3	13	18	9	16	8	4	2	1
23	13		13	8	12	18	4	6	9	2	3	16	1	13	8	12	18	4	6	9	2	3	16	1
23	14		14	12	7	6	15	3	19	13	21	18	22	9	11	16	17	8	20	4	10	2	5	1
23	15		15	18	17	2	7	13	11	4	14	3	22	8	5	6	21	16	10	12	19	9	20	1
23	16		16	3	2	9	6	4	18	12	8	13	1	16	3	2	9	6	4	18	12	8	13	1
23	17		17	13	14	8	21	12	20	18	7	4	22	6	10	9	15	2	11	3	5	16	19	1
23	18		18	2	13	4	3	8	6	16	12	9	1	18	2	13	4	3	8	6	16	12	9	1
23	19		19	16	5	3	11	2	15	9	10	6	22	4	7	18	20	12	21	8	14	13	17	1
23	20		20	9	19	12	10	16	21	6	5	8	22	3	14	4	11	13	7	2	17	18	15	1
23	21		21	4	15	16	14	18	10	3	17	12	22	2	19	8	7	9	5	13	20	6	11	1
23	22		22	1	22	1	22	1	22	1	22	1	22	1	22	1	22	1	22	1	22	1	22	1