Hi,

I need some advice & suggestions on how to represent the finite field GF(2^ operations (such as addition, inversion, multiplication) in binary representation in C language. Another thing is how to represent the pseudocode for generating multiplicative inverse below:

remainder[1] = f(x)
remainder[2] = a(x)
auxiliary[1] = 0
auxiliary[2] = 1

i = 2

do while remainder[i] <> 1
i = i + 1
remainder[i] = remainder(remainder[i-2] / remainder[i-1])
quotient[i] = quotient(remainder[i-2] / remainder[i-1])
auxiliary[i] = quotient[i] * auxiliary[i-1] + auxiliary[i-2]
inverse = auxiliary[i]

For AES, the f(x) = x^8 + x^4 + x^3 + x + 1.

Thank you & Regards.

-- Tiza --

Hi,

Anybody have an idea on how to start writing a C code for generating
the inverse of finite field GF(2^8 ) using extended Euclidean algorithm?
What I mean is how to represent a polynomial, e.g. f(x)=x^8+x^4+x^3+x+1
in C? How to represent the multiplication & division process of
polynomial?

Regards.

-- Tiza --

For future reference, the moderators generally frown upon posting more than one thread with the same question. Sometimes it takes a little while for someone who is knowledgeable about your question to see the thread, have time to respond, and work up a response. Be patient, then maybe reply to your own thread to bring it to the top of the list again if you want to draw more attention to it.

As for your question, the answer is: you can represent a polynomial in whatever way you can think of. There is usually not a single correct answer when it comes to questions of how to design something.

I'll offer a specific example of how I might approach this, but you should decide what is right for you and your application, and whether or not there might be a better approach.

First I would start by asking what defines a polynomial; that is, what makes it what it is. Well, the coefficient and the exponents pretty much capture everything you need to know. The highest exponent is typically given special significance, and called the degree, or order, of the polynomial.

One idea is to use an array to store the coefficients and let the array index represent the exponent of the term to which that coefficient applies. Note that for this we have to include zeros (0) for the terms that do not appear, up to the polynomial's degree. The size of the array will be the degrre of the polynomial plus 1. For your sample polynomial (writing it backwards so we can see more easily how is translates to an array), we use
(1 * x^0) + (1 * x^1) + (0 * x^2) + (1 * x^3) + (1 * x^4) + (0 * x^5) + (0 * x^6) + (0 * x^7) + (1 * x^8 )
So, the array contains (with the index listed above the element)

It might seem like a waste of space to store the zero coefficients, especially for high order polynomials with only a few non-zero terms. But the extra storage is very minimal (who is going to be dealing with polynomials of degree 1000?). Any approach that tries to store only what is needed will almost certainly have MORE overhead rather than less for typical polynomials.

Now, the arithmetic operations become pretty straightforward, since you can just move through the array picking up the exponent and coefficient for each term of the polynomials.

In C++, I would use an object-oriented design, with a class that represents the polynomials and probably using operator overloading to implement the arithmetic operations.

If working in C only, I would just implement functions for the arithmetic operations that take as arguments the degree and the array of coefficients for each polynomial. Maybe a prototype would look like this:Note that the last two parameters are for returning the new polynomial. You could also pass the size of the array itself (degree plus 1) rather than the degree, and make the appropriate adjustments to the function body.

However, I would choose C++ rather than C, if there is a choice.

If you can and want to use C++ instead, I would be willing to share some code ideas for that as well.

Matthew


* EDITED for typos *

No, bumping your thread is also frowned upon.

Sorry, actually I have been putting the same thread title because I thought that the previous question / thread is not really focussed to what I really need.

All you need to do is focus the question then. Posts are read no matter how deep they are.

Sorry if I unintentionally promoted a behavior that is not acceptable.

Matthew