Re: Multiplication trick in GF(2^m)
- From: Phil Carmody <thefatphil_demunged@xxxxxxxxxxx>
- Date: 27 Jun 2007 11:55:45 +0300
Manuel Pancorbo Castro <mpancorbo@xxxxxxxxx> writes:
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
I'm with you here,
sx^2 = x^(m+1) + x^(n+1)
= x.(x^m) + x^(n+1)
= x.(x^n+1) + x^(n+1)
= x
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.
But we're in a field? There is no remainder, everything (non-zero) divides
everything?
And surely the modular multiplication of A*B (mod P) can be done very
efficiently because P is a trinomial, anyway?
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).
I don't see that as having a lower bit-operation count than the
usual method. You still need to do 3 half-length multiplies, as
you would with a Karatsuba approach anyway.
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.
Aren't FFT techniques used? They scale better than Karatsuba.
Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.
.
- Follow-Ups:
- Re: Multiplication trick in GF(2^m)
- From: Manuel Pancorbo
- Re: Multiplication trick in GF(2^m)
- References:
- Multiplication trick in GF(2^m)
- From: Manuel Pancorbo Castro
- Multiplication trick in GF(2^m)
- Prev by Date: if you will regret Rudy's outlet beyond recordings, it will forwards stamp the matter
- Next by Date: Re: The Simplicity of it - Adacrypt
- Previous by thread: Multiplication trick in GF(2^m)
- Next by thread: Re: Multiplication trick in GF(2^m)
- Index(es):
Relevant Pages
|
