# GCM with reversed poly

These slides talk about how GCM can be sped up if one uses $$x^{128}+x^{127}+x^{126}+x^{121}+1$$ as the reduction polynomial instead of $$x^{128}+x^7+x^2+x^1+1$$.

When one is doing that one needs to multiply the polynomial you're attempting to reduce by $$x^{-127}$$, "better written as" $$x \cdot x^{-128}$$. I have three questions about this...

• Does this need to be done in addition to and prior to the method described on page 20 of those slides? Like do I need to explicitly multiply every polynomial I'm trying to reduce (let's call this polynomial $$y$$) by $$x^{-1}$$ and add $$y \ll 1$$ and $$y \ll 128$$? My assumption is that it does but idk

• When page 20 of those slides say $$x_0 \cdot C200000000000000_{16}$$ does it mean to do integer multiplication or polynomial multiplication? Like with integer multiplication $$5\cdot5=25 = 19_{16}$$ whereas with polynomial multiplication over a binary finite field $$5 \cdot 5$$ could be interpreted as $$(x^2 + 1)(x^2 + 1) = x^4+ x^2 + x^2 + 1 = x^4 + 1 = 11_{16}$$. I'm assuming you're supposed to do integer multiplication but idk

• Is $$C200000000000000_{16}$$ supposed to be in big endian format or little endian format? I'm guessing little endian since that's what GCM uses? In that scenario then $$C200000000000000_{16}$$ could be rewritten more simply as $$C2_{16}$$ just as $$0099$$ can be rewritten as $$99$$.

• Hint: $x^{-1}$ is the number that multiplied by $x$, modulo the reduction polynomial, makes $1$. You can find it and then compute its powers to obtain $x^{-2},...,x^{-127}$. However I believe that in this specific case the trick is to understand Montgomery reduction and that $R=x^{128}$ – Ruggero Jan 8 '19 at 13:58
• I can't help linking this fantastic blog post dissecting Gueron's trick: blog.quarkslab.com/… – SquareRootOfTwentyThree Jan 8 '19 at 21:00