FPGA Central

Hi,

I want to implement an extended Euclidean algorithm in MATLAB that can
compute the following: GCD(A(x),B(x)) = u(x)A(x) + v(x)B(x), where
A(x), B(x), u(x) and v(x) are from GF(2^m).

I have a basic understanding how this works for integers, but don't
want to re-invent the wheel for the above case. I did a search on
IEEEXPLORE, and the closest hit that I got was from Mandelbaum,
although this was a hardware implementation. Does anyone have perhaps
pointers to literature where this is clearly explained?

(I once got a glimpse of such a technique in a textbook, but I spent
the whole morning trying to find the book in the library without
success. It did something with a matrix)

I will greatly appreciate any suggestions and help
Jaco

Jaco Versfeld schrieb:
>
> Hi,
>
> I want to implement an extended Euclidean algorithm in MATLAB that can
> compute the following: GCD(A(x),B(x)) = u(x)A(x) + v(x)B(x), where
> A(x), B(x), u(x) and v(x) are from GF(2^m).

You could use gcd from PARI-GP
hth
Klaus

>
> I have a basic understanding how this works for integers, but don't
> want to re-invent the wheel for the above case. I did a search on
> IEEEXPLORE, and the closest hit that I got was from Mandelbaum,
> although this was a hardware implementation. Does anyone have perhaps
> pointers to literature where this is clearly explained?
>
> (I once got a glimpse of such a technique in a textbook, but I spent
> the whole morning trying to find the book in the library without
> success. It did something with a matrix)
>
> I will greatly appreciate any suggestions and help
> Jaco

Hello Jaco,

Try looking at "Prime Numbers" by Crandall and Pomerance. They present the
basic algo with some improvements. Are you trying to find inverses or GCDs?

Clay



"Jaco Versfeld" <[email protected]> wrote in message
news:[email protected] om...
> Hi,
>
> I want to implement an extended Euclidean algorithm in MATLAB that can
> compute the following: GCD(A(x),B(x)) = u(x)A(x) + v(x)B(x), where
> A(x), B(x), u(x) and v(x) are from GF(2^m).
>
> I have a basic understanding how this works for integers, but don't
> want to re-invent the wheel for the above case. I did a search on
> IEEEXPLORE, and the closest hit that I got was from Mandelbaum,
> although this was a hardware implementation. Does anyone have perhaps
> pointers to literature where this is clearly explained?
>
> (I once got a glimpse of such a technique in a textbook, but I spent
> the whole morning trying to find the book in the library without
> success. It did something with a matrix)
>
> I will greatly appreciate any suggestions and help
> Jaco

Jaco Versfeld wrote:
> I want to implement an extended Euclidean algorithm in MATLAB that can
> compute the following: GCD(A(x),B(x)) = u(x)A(x) + v(x)B(x), where
> A(x), B(x), u(x) and v(x) are from GF(2^m).
>
> I have a basic understanding how this works for integers, but don't
> want to re-invent the wheel for the above case. I did a search on
> IEEEXPLORE, and the closest hit that I got was from Mandelbaum,
> although this was a hardware implementation. Does anyone have perhaps
> pointers to literature where this is clearly explained?

for code: google "extended euclid"

http://www.geocities.com/SiliconVall...at/a_exeu.html
http://www-cse.uta.edu/~cook/aa/lect...23/node17.html

for explanation

Knuth, Seminumerical algorithms
Cormen, Leiserson, Rivest, and Stein, Intro to Algorithms

Mitch

Hi Jaco,

"Jaco Versfeld" <[email protected]> wrote in message
news:[email protected] om...
> Hi,
>
> I want to implement an extended Euclidean algorithm in MATLAB that can
> compute the following: GCD(A(x),B(x)) = u(x)A(x) + v(x)B(x), where
> A(x), B(x), u(x) and v(x) are from GF(2^m).

This is a lot easier than it may seem from a glance at the literature. I
assume you mean that the coefficients of those polynomials are in GF(2^m)?
The ring of polynomials with coefficients in GF(2^m) is usually written
GF(2^m)[x]. Everything below is valid for polynomials with coefficients in
any field, which you can verify by inspection, because I was careful to use
the proper signes for everthing even though addition and subtraction are the
same in GF(2^m):

Start with u=1,v=0, p=0,q=1, a=A and b=B.

Then iterate, always maintaining the invariants:

uA+vB=a; and
pA+qB=b

for each iteration:

if deg(a) < deg(b), then swap u <-> p, v <-> q, and a <-> b, so that
deg(a)>=deg(b) and the invariants are maintained.

If b==0, then stop. you're done.

Otherwise, "divide" to find a' and k such that a'=a-kb and deg(a')<deg(a).
(** see note **)

Then expand to get a'=uA+vB-kpA-kqB

and replace a <- a', u <- u-kp, and v <- v-kq

then repeat.

**note** You don't necessarily need to do a whole division here. It
suffices to ensure that the stated conditions are met. In particular, you
may simply choose k=x^(deg(a)-deg(b)) * (highest_coef(a)/highest_coef(b)).

This won't really save you any execution time, because you will keep
iterating until you have essentially done the long division, but it may save
you some code, and it doesn't hurt the worst case complexity, no matter what
nifty division algorithm you might have used instead.

If you need proof that the algorithm converges to the GCD, that's easy. The
only operations we perform on a and b are swapping a <-> b and replacing a
<- a-kb. GCD(a,b) = GC(b,a), so swapping a and b doesn't change the GCD.
And if d divides a and d divides b, then d divides a-kb, or a-kb is zero.
If a-kb is zero, then GCD(a,b) = b. So GCD(a,b) is preserved throughout the
algorithm until one of them gets to zero, at which point the other is the
GCD.

Oh, I forgot. You may get a scalar GCD that isn't 1. It still counts as
"greatest", because we're using degree for magnitude and it has degree 0.
If you need uA+vB=1, i.e., you're calculating an inverse, then just divide
everything by that scalar at the end.

Thanks a lot for all the suggestions. I appreciate it greatly.
Thanks for the algorithm, Matt. I implemented it and it works quite
nice.






[email protected] (Jaco Versfeld) wrote in message news:<[email protected] com>...
> Hi,
>
> I want to implement an extended Euclidean algorithm in MATLAB that can
> compute the following: GCD(A(x),B(x)) = u(x)A(x) + v(x)B(x), where
> A(x), B(x), u(x) and v(x) are from GF(2^m).
>
> I have a basic understanding how this works for integers, but don't
> want to re-invent the wheel for the above case. I did a search on
> IEEEXPLORE, and the closest hit that I got was from Mandelbaum,
> although this was a hardware implementation. Does anyone have perhaps
> pointers to literature where this is clearly explained?
>
> (I once got a glimpse of such a technique in a textbook, but I spent
> the whole morning trying to find the book in the library without
> success. It did something with a matrix)
>
> I will greatly appreciate any suggestions and help
> Jaco