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.

  • $\begingroup$ Does this answer help? $\endgroup$
    – Conrado
    May 13, 2020 at 13:52
  • 2
    $\begingroup$ Does this answer your question? GCM cipher M0 tables : semantic questions on how to implement GCM $\endgroup$
    – kelalaka
    Feb 5, 2021 at 16:22
  • $\begingroup$ Please indicate if the given answer or previous Q/A's answered your question. $\endgroup$
    – Maarten Bodewes
    Feb 18, 2021 at 23:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Feb 27, 2023 at 10:38

1 Answer 1


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.