# GCM Create M tables and R

I am trying to optimize GCM multiplication. This PDF explains GCM:

The Galois/Counter Mode of Operation (GCM)

The algorithms are in section 4.1

1. In algorithm 3 I have to multiply table M [128] with the element P that represents the polynomial α. Formulas (3) and (4) appear on page 9. From what I can understand, this would be:
**if V127 =0 then V ← rightshift(V )


else V ← rightshift(V ) ⊕ R**

The polynomial f would be 0xe1, no?

But in algorithm 3 I do not understand this: M[i] ← M[2i] · P. What would be the value of the element P if it corresponds to the polynomial α?

Hopefully, someone knows some code of the implementation of the tables that I can read. I have not found any code that can help me understand all of this.

• Does this answer help? May 13, 2020 at 13:52
• Does this answer your question? GCM cipher M0 tables : semantic questions on how to implement GCM Feb 5, 2021 at 16:22
• The document cited in the question had at least one update, formerly hosted by NIST, archived there. Some of the changes seem to be significant. It is still cited by the current spec.
– fgrieu
Feb 27, 2023 at 10:38

The polynomial f would be 0xe1, no?

it is $$e1 \mathbin \|0^{120}$$ i.e. 0xe1000000000000000000000000000000

What would be the value of the element P, if it corresponds to the polynomial α?

it is 2 reversed i.e. 0x40000000000000000000000000000000

• Could you turn the belief into reality? Feb 5, 2021 at 16:42
• @kelalaka updated Feb 6, 2021 at 21:32
• and references? Feb 6, 2021 at 21:33
• @kelalaka The response based on my own understanding of the paper mentioned in the question. There is no other references. Feb 8, 2021 at 22:29
• if 0xE1 ($11100001_b$) represents $x^7+x^2+x+1$ then 0x40 ($01000000_b$) represents $x$ Oct 25, 2023 at 7:05