Need help understanding math behind Rijndael S-Box in Rijndael SubBytes() step all bytes of input block are substituted based on a lookup table S-Box. S-Box is initialized by taking all elements of $GF(2^8)$, calculating their multiplicative inverse and then calculating their affine transform.
Here is C code which does that as found on wikipedia page.
#include &lt;stdint.h&gt;

#define ROTL8(x,shift) ((uint8_t) ((x) &lt;&lt; (shift)) | ((x) &gt;&gt; (8 - (shift))))

void initialize_aes_sbox(uint8_t sbox[256]) {
    uint8_t p = 1, q = 1;
    
    /* loop invariant: p * q == 1 in the Galois field */
    do {
        /* multiply p by 3 */
        p = p ^ (p &lt;&lt; 1) ^ (p &amp; 0x80 ? 0x1B : 0);

        /* divide q by 3 (equals multiplication by 0xf6) */
        q ^= q &lt;&lt; 1;
        q ^= q &lt;&lt; 2;
        q ^= q &lt;&lt; 4;
        q ^= q &amp; 0x80 ? 0x09 : 0;

        /* compute the affine transformation */
        uint8_t xformed = q ^ ROTL8(q, 1) ^ ROTL8(q, 2) ^ ROTL8(q, 3) ^ ROTL8(q, 4);

        sbox[p] = xformed ^ 0x63;
    } while (p != 1);

    /* 0 is a special case since it has no inverse */
    sbox[0] = 0x63;
}

I cant wrap my head around how multiplicative inverse is being calculated here. I assume p here acts as input while q is its inverse. Hence $p*q = 1$.
I want to understand how exactly this works because I am trying to implement a function that initializes Rijndael inverse S-Box, where first the inverse affine transform is calculated and then the multiplicative inverse.
The code is using the fact that the Rijndael's* Galois field has the following generators†:

3 5 6 9 11 14 17 18 19 20 23 24 25 26 28 30 31 33 34 35 39 40 42 44 48 49 60 62 63 65 69 70 71 72 73 75 76 78 79 82 84 86 87 88 89 90 91 95 100 101 104 105 109 110 112 113 118 119 121 122 123 126 129 132 134 135 136 138 142 143 144 147 149 150 152 153 155 157 160 164 165 166 167 169 170 172 173 178 180 183 184 185 186 190 191 192 193 196 200 201 206 207 208 214 215 218 220 221 222 226 227 229 230 231 233 234 235 238 240 241 244 245 246 248 251 253 254 255

A multiplicative generator $g$ means that $\langle g \rangle$ generates all of the element of $\operatorname{GF}(2^8) \text{ - } \{0\}$ or equivalently, $\mathbb{F}_{2^8}^*$. More formally, they form the cyclic multiplicative group of the finite field. The zero case handled at the end.
The choice of 3 in the code
/* multiply p by 3 */
p = p ^ (p &lt;&lt; 1) ^ (p &amp; 0x80 ? 0x1B : 0); 

is simply due to the optimization that 3 enables the smallest calculations to generate all of the elements. The 3 is actually a numerical expression of $x+1 \in \operatorname{GF}(2^8)$ in polynomial representation. Therefore, the above code is the multiplication of the current $p$ with $x+1$ as p ^ (p &lt;&lt; 1). The ^ (p &amp; 0x80 ? 0x1B : 0) part is the reduction with the primitive polynomial of the field by the equality $x^8 = x^4 + x^3 + x + 1$, in hex 0x1B where $x^8 + x^4 + x^3 + x + 1$ is the irreducable AES polynomial to that used to extend $\operatorname{GF}(2)$ to $\operatorname{GF}(2^8)$
The code is also using the fact that ;
$$1 = pq=pq \cdot 3 \cdot 3^{−1}=3p \cdot 3^{−1}q=1$$ now call $p′=3p$ and $q′ = 3^{−1}q$ and get $p′q′=1$. In this way, $p$ and $q$ get all valus of the table - expect 0 - since 3 is a generator. Then, by using the $q$, the affine transformation is computed for the table.
What is the advantage here?

No need to find the inverse by using the Ext-GCD or its better versions.
No multiplication is used for generating the elements.


* Rijndael $\neq$ AES (Actually, Rijndael $\supseteq$ AES). Rijndael is an AES candidate that won the competition and standardized as AES. The Rijndael is designed for  128, 192, or 256  key and block sizes. The AES has fixed block size 128 and have the  128, 192, or 256 bits key sizes.
† SageMath code to find all of those generators. Need sorting.
R.&lt;x&gt; = PolynomialRing(GF(2), 'x')
S.&lt;y&gt; = GF(2^8, modulus=x^8+x^4+x^3+x+1, repr='int')   

for i,x in enumerate(S):
    if x == 0:
        continue
    if x.multiplicative_order() == 255:
        print(&quot;{} {}&quot;.format(i, x))