Elke element van \(\textbf{GF}({2^n}) \setminus \{0\}\) heeft een inverse voor de vermenigvuldiging.

Indien \(\alpha\) een generator is van de groep \((\textbf{GF}({2^n}) \setminus \{0\}, \cdot)\), dan kan je dit inverse element vrij eenvoudig berekenen.

Schrijf de functie inverse_galois(g: int, h: str) -> int die de inverse berekent van een element g in \(\textbf{GF}(2^n)\). De parameter h bevat de coëfficienten van de monische irreduciebele veelterm \(h(x)\), voorgesteld als bitstring. Je mag hier veronderstellen dat \(\alpha\) een generator is van de groep \((\textbf{GF}({2^n}) \setminus \{0\}, \cdot)\).

Tip: stel het element voor als macht van \(\alpha\) en merk op dat \(\alpha^{2^n - 1} = 1\).

Voorbeelden:

Voor \(h(x) = x^4 + x + 1\) is \(h =\) “\(10011\)” en is \(\alpha\) een generator.

Om de inverse van \(6 = (100)\) te berekenen zet je dit element om naar een macht: \((100) = \alpha^5\). Dan is de inverse \(\alpha^{15-5} = \alpha^{10} = (0111) = 7\).

>>> inverse_galois(6, "10011")
7

Voor \(h(x) = x^4 + x^3 + 1\) is \(h =\) “\(11001\)” en is \(\alpha\) een generator.

Om de inverse van \(9 = (1001)\) te berekenen zet je dit element om naar een macht: \((1001) = \alpha^4\). Dan is de inverse \(\alpha^{15-4} = \alpha^{11} = (1101) = 13\).

>>> inverse_galois(9, "11001")
13