How to perform the modular reduce of Rijndael's finite field I am trying to understand how to calculate the modular reduction of Rijndael's finite field.

The example on this page says that {53} • {CA} = {01}, because (11111101111110 mod 100011011) = {3F7E mod 11B} = {01} = 1.

I am able to get to the point where I have 3F7E mod 11B, but cant seem to figure out how the reduction works.

      11111101111110 (mod) 100011011
     ^100011011     
       1110000011110
      ^100011011    
        110110101110
       ^100011011   
         10101110110
        ^100011011  
          0100011010 
          ^100011011 &lt;-- here, right shifted two places?
            00000001


From this example, why does it right shift two places at one point?

I also found an example that 0x1b*0xaa equals 0x8c. Trying to solve this myself I get to the point: 0xE0E mod 0x11B

 111000001110
^100011011
  11011010110
 ^100011011
   1010111010
  ^100011011
    010001100
   ^100011011
     10010111


This makes it 0x97
First let us have a look at the division of $\mathtt{0x3f7e}$ by $\mathtt{0x11b}$

1      11111101111110 |    (mod) 100011011
2     ^100011011      +-----------------------
3     +-------------+ |          1?????
4       1110000011110 |                &gt;&gt; 1
5      ^100011011     |
6      +------------+ |          11????
7        110110101110 |                &gt;&gt; 1
8       ^100011011    |
9       +-----------+ |          111???
10        10101110110 |                &gt;&gt; 1
11       ^100011011   |
12       +----------+ |          1111??
13         0100011010 |                &gt;&gt; 1
14        ^000000000  |
15        +---------+ |          11110?
16          100011010 |                &gt;&gt; 1
17         ^100011011 |
18         +--------+ |          111101
19           00000001 |


The result of the Euclidean division is therefore:
$$\mathtt{0x3f7e} = \mathtt{0x11b} \times \mathtt{0x3d} + \mathtt{0x1}$$
Or :
$$\mathtt{11111101111110} = \mathtt{100011011} \times \mathtt{111101} + \mathtt{1}$$
Thus:
$$\mathtt{11111101111110} \equiv 1 \pmod{\mathtt{100011011}}$$

As we don't care of the result of the division but only of the residue, we directly forget it.

As you noticed each line there is a single right shift (&gt;&gt; 1) in the subtraction. But also notice that when a bit of the quotient is 0, nothing is being done after this right shift  (see lines $\texttt{12}$ to $\texttt{15}$) (because we multiply the divisor by 0, the result will obviously be the same after the subtraction... by 0).

Thus we can factorize the lines $\texttt{14}$ to $\texttt{16}$ by double right shift (&gt;&gt; 2), giving us the Wikipedia division:

1      11111101111110 |    (mod) 100011011
2     ^100011011      +-----------------------
3     +-------------+ |          1?????
4       1110000011110 |                &gt;&gt; 1
5      ^100011011     |
6      +------------+ |          11????
7        110110101110 |                &gt;&gt; 1
8       ^100011011    |
9       +-----------+ |          111???
10        10101110110 |                &gt;&gt; 1
11       ^100011011   |
12       +----------+ |          1111??
13         0100011010 |                &gt;&gt; 2
17         ^100011011 |
18         +--------+ |          111101
19           00000001 |


TL;DR: the double right shift correspond to the $\mathtt{0}$es in the quotient.

About: $\mathtt{0x1b} \times \mathtt{0xaa} \equiv \mathtt{0x8c} \pmod{\mathtt{0x11b}}$



And looking back at your division:

1     111000001110
2    ^100011011
3      11011010110
4     ^100011011
5       1010111010
6      ^100011011
7        010001100
8       ^100011011  &lt;-- THIS IS VERY WRONG
9         10010111  &lt;--


Lines $\texttt{8}$ and $\texttt{9}$ are simply not allowed:
$$\mathtt{10001100} &lt; \mathtt{10001101}$$
Thus $\mathtt{10001100}$ is the result and by a strange coincidence $\mathtt{10001100} = \mathtt{0x8c}$.