# Multiplicative inverse in $GF(2^8)$?

1. I know how to do multiplication over $GF(2^8)$.
Logic is...

uint8_t  gmul(uint8_t  a, uint8_t  b)
{
uint8_t p=0;
uint8_t carry;
int i;
for(i=0;i<8;i++)
{
if(b & 1)
p ^=a;
carry = a & 0x80;
a = a<<1;
if(carry)
a^=0x1b;
b = b>>1;
}
return p;
}


So, I created arithmetic in a $GF(2^8)$-Multiplication table. Given below the values in the 3rd raw, but I don't think it is true. I don't know what went wrong.

I multiplied first raw value with first column values.
Eg: in the third row, I multiplied 2*0, 2*1,.....2*e, 2*f.

    0  1  2  3  4  5  6  7   8  9  A  B  c  D  E  F
0
1
2   0  2  4  6  8  a  c  e  10 12 14 16 18 1a 1c 1e
3
.
.
E
F


How can I create arithmetic in a $GF(2^8)$ table for multiplication?

2. How can I find the multiplicative inverse in $GF(2^8)$.
Eg: the inverse of (95) = 8A?

-

The standard method for doing multiplication (and multiplicative inverses) in $GF(2^8)$ is using a log and antilog table. Each table takes up only 255 bytes; hence it is much smaller than a full $256 \times 256$ multiplication table, and it is much faster than the multiplication procedure you give above.

To create such tables, we need to pick a generator $g$; that is a field element such that $g^i$ is all 255 nonzero elements for $0 \le i < 255$ (where $g^i$ is what you would expect; $g$ multiplied by itself $i$ time). Such an element always exists, and (IIRC) $g=3$ happens to be a generator in the field representation you are using.

Now, the antilog table is defined as:

$$antilog(i) = g^i$$

This table has 255 elements, and can be easily built using your multiplication procedure. You may want to extend it farther (as discussed below); it just continues in the obvious way (and it just repeats itself).

The log table is defined as its inverse, that is:

$$antilog(log(i)) = i$$

This table also has 255 elements (but is indexed from 1 to 255), and can be built using the antilog table we already have.

Once we have those two, we can do multiplication by:

    uint8_t gmul_table(uint8_t a, uint8_t b)
{
if (a == 0 || b == 0) return 0;

uint8_t x = log(a);
uint8_t y = log(b);
uint8_t log_mult = (x + y) % 255;

return antilog(log_mult);
}


This works because, if $a = g^x$ and $b = g^y$, then $a \times b = g^x \times g^y = g^{x+y} = g^{(x+y) \bmod 255}$

As you can see, that should be considerably more efficient than your original algorithm; you can omit the $% 255$ operation by extending the antilog table for 255 more elements.

We can also use those tables to compute multiplicative inverses:

    uint8_t ginv_table(uint8_t a)
{
if (a == 0) return 0;   /* Error */

uint8_t x = log(a);
uint8_t log_inv = (255 - x) % 255;

return antilog(log_inv);
}


You can also compute inverses using the Extended Euclidean Algorithm (which can be adapted to work in $GF(2^8)$; however it's considerably more work than two table lookups.

Here is how that algorithm would look like:

    uint8_t ginv(uint8_t x)
{
uint16_t u1, u3, v1, v3;

u1 = 0; u3 = 0x11b;
v1 = 1; v3 = x;

for (;;) {
uint16_t t1, t3, x, y;

if (v3 == 0) break;

x = u3; x |= x>>1; x |= x>>2; x |= x>>4;
y = v3; y |= y>>1; y |= y>>2; y |= y>>4;
if (x >= y) {
uint16_t z = x & ~y;
uint8_t q = numbits(z);
t1 = u1 ^ (v1<<q);
t3 = u3 ^ (v3<<q);
} else {
t1 = u1;
t3 = u3;
}
u1 = v1; u3 = v3;
v1 = t1; v3 = t3;
}

if (u1 >= 0x100) u1 ^= 0x11b;

return u1;
}


(where numbits(x) returns the number of bits set in x)

-
i included "#include<math.h>" then too i get the following error- undefined reference to `antilog'. can you explain(with code)how to compute using euclidean algorithm. i know the extended euclidean alogorithm, but don't know how to implement in binaries? –  Melvin Jan 17 '14 at 2:08
Actually, log and antilog are tables that you build (or initialize); they're uint8_t log[255], antilog[255]; (and, come to think about it, in C, log isn't the best name; it conflicts with the log() function within math.h). You initialize those tables as above (possibly using your multiplication routine to generate the initial antilog entries) –  poncho Jan 17 '14 at 2:29
k will do, but can you show me code using extended euclidean algorithm to show multiplicative inverse? –  Melvin Jan 17 '14 at 3:12
hot to create antilog(log_inv) function? you said to create uint8_t log[255] which is an array,then how will antilog(log_inv)call will work? how to implement it? if any other ways are there please show me –  Melvin Jan 17 '14 at 10:57

The multiplication table has $2^8 = 256$ rows and columns. You are doing the multiplication right, but you have not filled the entire third row yet (there must be 256 elements).

To find the inverse of $A$, you find $B$ such that $A*B = 1$ in your multiplication table (there are other algorithms for inversion, but you might not need them for such a small field).

-
can you give any of the inversion algorithm? –  Melvin Jan 17 '14 at 2:10
inverse of 95 is 8A. but when i took 9th row and 5th column in multiplication table i got 2D. So A*B !=1. then how to fidn out inverse of 95? –  Melvin Jan 17 '14 at 10:49
You have a multiplication table. And you look for entries $9$ and $5$. That means you compute a value $9\cdot 5= 2D$ (or 45 in decimal). This has nothing to do with the inverse of $95$. If you have a full multiplication table, then you look at row $95$, and find in this row the entry "1". The column of this entry is the inverse element. Btw as others said before, $GF(2^8)$ has 256 elements, not 16. –  tylo Jan 17 '14 at 16:39