The Laws of Cryptography:
Compare Multiplication Results

by Neal R. Wagner

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

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() {
}

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];
}

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;
}
}

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();
}
}
```

Revision date: 2001-12-28. (Please use ISO 8601, the International Standard.)