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@Radix.Net