Maamoun TK maamoun.tk@googlemail.com writes:
Hi Niels,
I tried to apply your method but can't get it work,
Hmm, do you think I've missed something in the math, or are there other difficulties?
while applying it one question came to my mind.
First, compute b_0(x) / x^64 (mod P(x)), which expands it from 64 bits to 128,
c_1(x) x^64 + c_0(x) = b_0(x) / x^64 (mod P(x))
Here you are trying to get partially reduced product by computing b_0(x) / x^64 (mod P(x)) but since the degree of input is 127, we can use the polynomial defining the finite field with x^64 elements, in this case P(x) = X^64+X^4+X^3+X+1 and P' = P^-1 (mod X^64) = X^63+X^61+X^60+1 which is the same constant 0xB0 and the function now: c_1(x) x^64 + c_0(x) = ((b_0 mod X^64) * p') mod X^64
For correctness, I think it is important that the computation b_0(x) / x^64 is done modulo the gcm polynomial (originally, x^128 + x^7 + x^2 + x + 1, but after bit reflection, P(x) = x^128 + x^127 + x^126 + x^125 + 1).
I don't see how one can do part of the computation in GF(2^64), or how your degree-64 polynomial relates the the original degree-128 polynomial. If there's some useful embedding of GF(2^64) as a subfield of GF(2^128), please explain?
That said, division by x^64 is fairly cheap, since P(x) = 1 (mod x^64). I think we get
b_0(x) / x^64 (mod P(x)) = b_0(x) (1 + P(x)) / x^64 (mod P(x)
where we can simplify (P(x) + 1) / x^64 to x^64 + x^63 + x^62 + x^58, or
b_0(x) / x^64 (mod P(x)) = b_0(x) (x^64 to x^64 + x^63 + x^62 + x^58)
So no reduction needed, just split the product in high and low part to get c_1 and c_0.
Regards, /Niels