1.7 KiB
Extended Euclidean Algorithm
EEA Cycle Estimates
Main loop body: 25 (N times) swap_and_negate: 22 (S times) gf_degree: 10 (twice per loop) Number of Loops: N
\ext{Total Cycles} = N \times (25 + 2 \times 10) + S \times 22
Pseuo-Code
r0 := m r1 := a s0 := 0 s1 := 1
while r1 \neq 0: deg_r0 = degree(r0) deg_r1 = degree(r1) shift = deg_r0 - deg_r1
if shift < 0:
swap(r0, r1)
swap(s0, s1)
shift := -shift
r0 = r0 ^ (r1 << shift)
s0 = s0 ^ (s1 << shift)
if r0 \neq 1: return "No inverse" else: return s0
LaTeX
\documentclass{article} \usepackage{algorithm} \usepackage{algpseudocode} \usepackage{amsmath}
\begin{document}
\begin{algorithm}
\caption{Extended Euclidean Algorithm in GF(2\textsuperscript{8})}
\begin{algorithmic}[1]
\Require Input value a, modulus m (usually 0x11B)
\Ensure Return s_0 such that s_0 \cdot a \equiv 1 \pmod{m} if inverse exists
\State r_0 \gets m
\State r_1 \gets a
\State s_0 \gets 0
\State s_1 \gets 1
\While{$r_1 \ne 0$}
\State d_0 \gets \text{deg}(r_0)
\State d_1 \gets \text{deg}(r_1)
\State \text{shift} \gets d_0 - d_1
\If{$\text{shift} < 0$}
\State Swap $r_0 \leftrightarrow r_1$
\State Swap $s_0 \leftrightarrow s_1$
\State $\text{shift} \gets -\text{shift}$
\EndIf
\State $r_0 \gets r_0 \oplus (r_1 \ll \text{shift})$
\State $s_0 \gets s_0 \oplus (s_1 \ll \text{shift})$
\State Mask $r_0$ and $s_0$ to 9 bits: $r_0 \gets r_0 \mathbin{\&} 0x1FF$, $s_0 \gets s_0 \mathbin{\&} 0x1FF$
\EndWhile
\If{$r_0 = 1$}
\State \Return s_0 \Comment{Inverse found}
\Else
\State \Return \textbf{error} \Comment{No inverse exists}
\EndIf
\end{algorithmic}
\end{algorithm}
\end{document}