polynomial extended euclidean algorithm

[Tiza Naziri]

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

[jacob navia]

Re: polynomial extended euclidean algorithm

Tiza Naziri wrote:[color=blue]
> 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 --
>[/color]
There are basically two ways:
1) Dense representation:
Use a vector of N+1 positions where N is the highest degree term.
In this case you would use a vector of 9 positions:
1 0 0 0 1 1 0 1 1
In a polynomial 5x^8 + 25x^4 + 567 you would have:
5 0 0 0 25 0 0 0 567
2) Sparse representation:
Use a linked list where each term is represented by a pair of
numbers exponent and constant term. This representation is better for
polynomials like 10x^200 + x + 5:
{ 200 10 } {1 1} { 0 5}

jacob

[BRG]

Re: polynomial extended euclidean algorithm

Tiza Naziri wrote:[color=blue]
> 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?[/color]

Let the bits in a variable represent powers of x so that, for example,
x^8+x^4+x^3+x+1 is represented by bits *, 4, 3, 1 and 0. In this case
we obtain 0x11b as the represntation of this polynomial.

Now if we want to add or subtract two such values, all we have to do is
to xor them together so that, for example:

'x + 1' + 'x^2 + x' ==> 0x003 xor 0x006 = 0x005 ==> x^2 + 1.

And multiplication by x is a shift left by one position. Finally if bit
8 is set after an operation we have to subtract (xor) 0x11b into the
result (assuming that 0x11b is our modular polynomial). Division can
then be represented by repeated subtraction.

If we want to divide GF(2^8) element T by element B, we shift left the B
variable until its top bit matches the top bit of T. We then xor the
result into T so that the top bit of T becomes zero. Now we can repeat
this again for the new value of T until T has fewer bits than B. The
resulting T value is the remainder of the division, while the quotient
is the 1 bits representing the multiples of B that we take away from T
in this process

The US FIPS document for the AES encryption algorithm explains this in
more detail.

Brian Gladman

[jacob navia]

Re: polynomial extended euclidean algorithm

BRG wrote:[color=blue]
>
> Let the bits in a variable represent powers of x so that, for example,
> x^8+x^4+x^3+x+1 is represented by bits *, 4, 3, 1 and 0. In this case
> we obtain 0x11b as the represntation of this polynomial.[/color]

Is it possible to represent

45x^8 + 1769x^3 + 7.976x + 3.14159

using that representation?

Maybe it is possible to restrain the domain of the
polynomial but that wasn't in the specs, at least in
the specs such as I understood them...

jacob

[Stephen Sprunk]

Re: polynomial extended euclidean algorithm

"jacob navia" <jacob@jacob.re mcomp.fr> wrote in message
news:42374858$0 $25042$8fcfb975 @news.wanadoo.f r...[color=blue]
> BRG wrote:[color=green]
> >
> > Let the bits in a variable represent powers of x so that, for example,
> > x^8+x^4+x^3+x+1 is represented by bits *, 4, 3, 1 and 0. In this case
> > we obtain 0x11b as the represntation of this polynomial.[/color]
>
> Is it possible to represent
>
> 45x^8 + 1769x^3 + 7.976x + 3.14159
>
> using that representation?[/color]

That representation can only handle coeffecients of one or zero, which are
all that are possible in certain fields of mathematics. Outside those
fields, such representation is unusable.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin

[Tiza Naziri]

Re: polynomial extended euclidean algorithm

Thanks, really appreciate the suggestions..

[Jack Klein]

Re: polynomial extended euclidean algorithm

On 14 Mar 2005 23:44:38 -0800, "Tiza Naziri" <watija@yahoo.c om> wrote
in comp.lang.c:
[color=blue]
> 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 --[/color]

Sure...

#include <stdio.h>

int main(void)

....at least that's how I'd start writing it.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++

http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html

[Tiza Naziri]

Re: polynomial extended euclidean algorithm

Hi Brian,

How do I measure the cycles needed for the written C code? Currently
I'm using Pentium 4 2GHz processor. Is there any special software for
it or it just can be measured using C?

Regards.

-- Tiza --

[jacob navia]

Re: polynomial extended euclidean algorithm

Tiza Naziri wrote:[color=blue]
> Hi Brian,
>
> How do I measure the cycles needed for the written C code? Currently
> I'm using Pentium 4 2GHz processor. Is there any special software for
> it or it just can be measured using C?
>
> Regards.
>
> -- Tiza --
>[/color]

The best way is to use the time stamp counter of
the processor.

The assembly instruction is called RDTSC. Some compilers
provide intrinsics to do that.

[BRG]

Re: polynomial extended euclidean algorithm

jacob navia wrote:[color=blue]
> BRG wrote:
>[color=green]
>>
>> Let the bits in a variable represent powers of x so that, for example,
>> x^8+x^4+x^3+x+1 is represented by bits *, 4, 3, 1 and 0. In this case
>> we obtain 0x11b as the represntation of this polynomial.[/color]
>
>
> Is it possible to represent
>
> 45x^8 + 1769x^3 + 7.976x + 3.14159
>
> using that representation?
>
> Maybe it is possible to restrain the domain of the
> polynomial but that wasn't in the specs, at least in
> the specs such as I understood them...[/color]

He explicitly said GF(2^8) ...

Brian Gladman

[BRG]

Re: polynomial extended euclidean algorithm

Tiza Naziri wrote:
[color=blue]
> Hi Brian,
>
> How do I measure the cycles needed for the written C code? Currently
> I'm using Pentium 4 2GHz processor. Is there any special software for
> it or it just can be measured using C?[/color]

As Jacob Navia has said, if you want to start from scratch then you need
to learn about the use of the RDTSC instruction and how to access this
in C.

In fact its quite hard to get good timing information but if you are
happy to learn how others time their code you might be interested in an
approach that Cristophe Devine and I use, which is provided in the
source code available at:

http://www.cr0.net:8040/code/crypto/aesbench/

This measures differential timing information over many runs and
averages the results whilst also watching to ensure that the standard
deviation in the timing information is not too large.

Brian Gladman

[CBFalconer]

Re: polynomial extended euclidean algorithm

jacob navia wrote:[color=blue]
> Tiza Naziri wrote:[color=green]
>>
>> How do I measure the cycles needed for the written C code?
>> Currently I'm using Pentium 4 2GHz processor. Is there any
>> special software for it or it just can be measured using C?[/color]
>
> The best way is to use the time stamp counter of
> the processor.
>
> The assembly instruction is called RDTSC. Some compilers
> provide intrinsics to do that.[/color]

Which instruction doesn't exist on a '486, for example, not to
mention MACs etc. Use of such causes illegal instruction traps.
So you should always guard any such use with detection of the
actual machine type in use.

Besides which this assembly diversion is all OT for c.l.c. It is
bad enough to get so far OT, but then to recommend practices that
cause crashes is totally reprehensible IMO.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Tiza Naziri]

Re: polynomial extended euclidean algorithm

Do you think that memory-reduction design of an encryption algorithm
could lead to the efficiency of software encryption implementation,
especially with limited memory devices such as smart card?

[Tiza Naziri]

Re: polynomial extended euclidean algorithm

Actually, this question relates to my actual question on how to code
the polynomial EEA. I intend to reduce the memory usage of S-box by
generating all of the values on-the-fly for every process in encryption
& decryption of AES.

[Randy Howard]

Re: polynomial extended euclidean algorithm

In article <4237EAEC.9AC25 75F@yahoo.com>, cbfalconer@yaho o.com
says...[color=blue]
> jacob navia wrote:[color=green]
> > Tiza Naziri wrote:[color=darkred]
> >>
> >> How do I measure the cycles needed for the written C code?
> >> Currently I'm using Pentium 4 2GHz processor. Is there any
> >> special software for it or it just can be measured using C?[/color]
> >
> > The best way is to use the time stamp counter of
> > the processor.
> >
> > The assembly instruction is called RDTSC. Some compilers
> > provide intrinsics to do that.[/color]
>
> Which instruction doesn't exist on a '486, for example, not to
> mention MACs etc. Use of such causes illegal instruction traps.
> So you should always guard any such use with detection of the
> actual machine type in use.
>
> Besides which this assembly diversion is all OT for c.l.c. It is
> bad enough to get so far OT, but then to recommend practices that
> cause crashes is totally reprehensible IMO.[/color]

It also can give completely bogus results when executed, even on
an Intel processor that supports RDTSC. Specifically, in the
case of an SMP platform. The TSC counters are not sync'd between
processors, so if your program gets bounced, the results can
effectively be no better than random or just making something up.

--
Randy Howard (2reply remove FOOBAR)
"Making it hard to do stupid things often makes it hard
to do smart ones too." -- Andrew Koenig