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

The Laws of Cryptography with Java Code.

There have been two algorithms for multiplying field elements, a slow one and a fast one. As a check, the following program compares the results of all 65536 possible products to see that the two methods agree (which they do):

// FFMultTest: test two different ways to multiply, all 65536 products
public class FFMultTest {
   public FFMultTest() {
      loadE();
      loadL();
   }

   public byte[] E = new byte[256]; // powers of 0x03
   public byte[] L = new byte[256]; // inverse of E
   private String[] dig = {"0","1","2","3","4","5","6","7",
                           "8","9","a","b","c","d","e","f"};

   // FFMulFast: fast multiply using table lookup
   public byte FFMulFast(byte a, byte b){
      int t = 0;;
      if (a == 0 || b == 0) return 0;
      t = (L[(a & 0xff)] & 0xff) + (L[(b & 0xff)] & 0xff);
      if (t > 255) t = t - 255;
      return E[(t & 0xff)];
   }

   // FFMul: slow multiply, using shifting
   public byte FFMul(byte a, byte b) {
      byte aa = a, bb = b, r = 0, t;
      while (aa != 0) {
         if ((aa & 1) != 0)
            r = (byte)(r ^ bb);
         t = (byte)(bb & 0x80);
         bb = (byte)(bb << 1);
         if (t != 0)
            bb = (byte)(bb ^ 0x1b);
         aa = (byte)((aa & 0xff) >> 1); 
      }
      return r;
   }

   // hex: print a byte as two hex digits
   public String hex(byte a) {
      return dig[(a & 0xff) >> 4] + dig[a & 0x0f];
   }

   // loadE: create and load the E table
   public void loadE() {
      byte x = (byte)0x01;
      int index = 0;
      E[index++] = (byte)0x01;
      for (int i = 0; i < 255; i++) {
         byte y = FFMul(x, (byte)0x03);
         E[index++] = y;
         // System.out.print(hex(y) + " ");
         x = y;
      }
   }

   // loadL: load the L table using the E table
   public void loadL() {
      int index;
      for (int i = 0; i < 255; i++) {
          L[E[i] & 0xff] = (byte)i;
      }
   }

   // testMul: go through all possible products of two bytes
   public void testMul() {
      byte a = 0;
      for(int i = 0; i < 256; i++) {
         byte b = 0;
         for(int j = 0; j < 256; j++) {
            byte x = FFMul(a, b);
            byte y = FFMulFast(a, b);
            if  (x != y) {
               System.out.println("a: " + hex(a) + ", b: " + hex(b) +
                                ", x: " + hex(x) + ", y: " + hex(y));
               System.exit(1);
            }
            b++;
         }
         a++;
      }
   }

   public static void main(String[] args) {
      FFMultTest ffmult = new FFMultTest();
      ffmult.testMul();
   }
}