Tuesday 29 December 2015

coding theory - Using Extended Euclidean Algorithm to find multiplicative inverse




Having some trouble working my way back up the Extended Euclidean Algorithm.
I'm trying to find the multiplicative inverse of $497^{-1} (mod 899)$. So I started working my way down first finding the gcd:



\begin{align}
899&=497\cdot1 + 402\\
497&=402\cdot1 + 95\\
402&=95\cdot4 + 22\\
95&=22\cdot4 + 7\\
22&=7\cdot3 + 1
\end{align}

Now I work my way back up using the extended algorithm and substituting:
\begin{align}
1&=22-(7\cdot3)\\
1&=22-(95-(22\cdot4))\cdot3\\
1&=22-(95-(402-(95\cdot4)\cdot4))\cdot3\\
1&=22-(95-(402-((497-402)\cdot4)\cdot4))\cdot3\\
1&=22-(95-(402-((497-(899-497))\cdot4)\cdot4))\cdot3\\
\end{align}



Am I going about this right? Do I just keep substituting up the chain? It gets difficult to follow for me. And

Here's what the terms equal going up:



\begin{align}
7&=95-(22\cdot4)\\
22&=402- ( 95\cdot4)\\
95&=497- 402\\
402&=899- 497\\
\end{align}


Answer



For an (iterative) implementation it is easier to compute the inverse resp. the Bezout coefficients while going down.




You start with $0·497 \equiv r_0=899\mod899$ and $1·497 \equiv r_1=497\mod899$ and apply the same sequence of computations as to the remainder to the quotient sequence starting with $u_0=0, u_1=1$.
\begin{align}
r_2&=r_0-1·r_1&\implies u_2&=u_0-1·u_1=-1 &:&&-1·497 &\equiv r_2=402\mod899
\\
r_3&=r_1-1·r_2&\implies u_3&=u_1-1·u_2=2 &:&&2·497 &\equiv r_3=95\mod899
\\
r_4&=r_2-4·r_3&\implies u_4&=u_2-4·u_3=-9 &:&&-9·497 &\equiv r_4=22\mod899
\\
r_5&=r_3-4·r_4&\implies u_5&=u_3-4·u_4=38 &:&&38·497 &\equiv r_5=7\mod899

\\
r_6&=r_4-4·r_5&\implies u_6&=u_4-3·u_5=-123 &:&&-123·497 &\equiv r_6=1\mod899
\end{align}
Thus the inverse is $-123$ or in the same equivalence class $899-123=776$


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...