Calculating Multiplicative Inverse for Rijndael S-box using EEA
To do EEA on a finite-field, you can't perform the operations using the operations in the ring of the integers (and they're not precisely the same operations in the field either, as you're working with bit vectors, not field elements).  In particular:


When you do "addition", you need to perform the addition as done in even characteristic fields (that is, you actually do an exclusive-or).
"Subtraction" is actually the same as "addition", so you use exclusive-or for that as well.  Yes; addition and subtraction are the same thing; we're not in Kansas anymore.
The "multiplication operation" is actually a bit shift, as so we would have something like:

new_r = old_r ^ (r &lt;&lt; quotient);


What you want is to have (r &lt;&lt; quotient) cancel out the msbit of old_r; To make this work, your 'divide' operation needs to effective compute how far the r needs to be shifted left so that the exclusive-or will cancel out the msbit (and hence reduce the size of r).
The test at the bottom (if t is out of range) looks differently.  It turns out (with the above changes) t will never be negative; it might be larger than 255


The Extended Euclidean algorithm can be made to work.  On the other hand, I'm having a hard time seeing a situation where it is a best algorithm for this job.  It's not nearly as fast as a simple table lookup, and it's not even slightly side channel resistant.