Multiplication trick in GF(2^m)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I present a trick to perform efficiently the operation

R(x) = A(x)*B(x) mod P(x)

where A,B,R are polynomials in GF(2^m)/P and P is the primitive trinomial

P = x^m + x^n + 1

where "m" and "n" are odd.

The goal is not to overflow the actual word size. The actual algorithms
calculates R' = A*B and then reduces the result R = R' mod P; so it is
needed a double-sized record. On the other side, it can be made at bit
level without overflow, but to the cost of too much shifts and xors. This
method does the things within single-sized records and without extensive
bit-level operations. Moreover, the performing speed can be also increased
as a side effect.

The key of the method is the square root of "x". For trinomials with "m"
and "n" odd it can be easily computed:

sqrt(x) mod P = x^s + x^t
with s = (m+1)/2, t = (n+1)/2

Then we split A and B as follows:

A = a0 + a1*sqrt(x)
B = b0 + b1*sqrt(x)

where a0, b0 are the remainders [A mod sqrt(x)] and [B mod sqrt(x)]; and a1,
b1 the quotients [A / sqrt(x)], [B / sqrt(x)]. These quotient/remainder
operations can be done very efficiently because sqrt(x) is a binomial. All
these polynomials have maximum degree (m-1)/2.

So we have:

A*B = a0*b0 + x*(a1*b1) + C*sqrt(x)

where C follows from the known Karatsuba's trick

C = (a0 + a1)*(b0 + b1) + a0*b0 + a1*b1

C is again splitted:

C = c0 + c1*sqrt(x)

so finally

R' = a0*b0 + x*(a1*b1 + c1) + c0*sqrt(x)

Notice that multiplication by sqrt(x) is very quick (two shifts and one
xor).

R' has degree at most "m" so:

if deg(R') == m then R = R' + P;
else R = R'.

Squaring is also trivially done:

A^2 mod P = (a0 + sqrt(x)*a1)^2 = a0^2 + x*a1^2

The method applies only to this kind of trinomial primitives with "m"
and "n" odd, but I think them very often in crytographic algorithms; "m"
uses to be prime and you can choose in most cases "n" as odd.

After somehow extensive google survey about optimal GF(2^m) multiplication,
I didn't find this matter documented anywhere; thus perhaps it is original.
Comments and references to previus similar works are welcome.

- --
Manuel Pancorbo Castro
http://sks.merseine.nu/


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: SKS pocket ECC. http://sks.merseine.nu/

iD8DBQFGgZJSWmnkWA8sPKsRAiNvAKDucc33HLgIG7dIMQKx+toH28OkSQCeM7IJ
wUL7uQjpWrUf0rQVeBDSAc8=
=qDt4
-----END PGP SIGNATURE-----
.

Relevant Pages