# Factorization of polynomial in GF(2^128) used in GCM

It is widely known, that using a GCM nonce twice or even more often can be used to disclose the authentication key H. I understand, why this is theoretically possible. However, I have no feeling about the computational effort behind obtaining polynomial roots in GF($$2^{128}$$). Is there a straightforward algorithm available or do we need to apply some brute-force methods to factor a given polynomial according to a given field polynomial.?

"Straightforward" is a relative term. There are algorithms. The basic outline for one of them is

1. First factor the polynomial into square-free factors using the Square-Free Factorization Algorithm.
2. For each square-free factor found in step 1, factor it into a products or factors of the same degree (Distinct Degree Factorization).
3. Use the Cantor-Zassenhaus algorithm to factor each result of step 2.

For a more detailed description see e.g. [Section 3.4, Cohen].

References:

[Cohen] Henri Cohen. A Course in Computational Algebraic Number Theory. Springer-Verlag, Berlin, 1993.

• Tis is what I was looking for ;-) Jul 20 at 7:01