Question on Galois Fields

[John A. Limpert]

At 12:13 PM 10/9/95 UTC+0100, you wrote:
>Can anyone explain or give an example of how to use arithmetic in GF(q^n)?
>
>Often in cryptography we work in GF(p). I knew the existence of other fields,
>like elliptic curves and so, but I found a short comment in Applied
>Cryptography page 210 that I couldn't understand.

I wrote a Reed-Solomon encoder that had to do addition and multiplication
over GF(2^8). Addition was simple, just a bitwise exclusive-or.
Multiplication required two tables, a log-alpha table and an alog-alpha
table. The product was computed by taking the anti-log of the sum of
the logs of the arguments. Both tables were 256x8 lookup tables. The table
contents were derived from the generator polynomial G(x) specified
for the encoder. Another two 256x8 tables were used to translate between
dual basis and conventional basis. Dual basis was specified for the
encoder to make a hardware implementation simpler but I found that it was
easier to use conventional basis for a software implementation.

Not being a mathematician, I used several NASA technical reports on
Reed-Solomon encoders and an excellent book on error correcting codes
by Lin & Costello to understand enough of the math to write the
encoder software. Galois fields are heavily used in the design of
error correcting codes.



--
John A. Limpert
johnl at Radix.Net