I am dealing with ECC in these days which heavily based on finite fields. I want to how to find a inverse of a value in finite field and what is multiplicative inverse and also Congruence
F29-
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27 28}
For any integer a, a mod p shall denote the unique integer remainder r , 0 ≤ r ≤ p − 1, obtained upon dividing a by p; this operation is called reduction modulo p.
(i) Addition: 17 + 20 = 8 since 37 mod 29 = 8
(ii) Subtraction: 17 − 20 = 26 since −3 mod 29 = 26
(iii) Multiplication: 17 · 20 = 21 since 340 mod 29 = 21
(iv) Inversion: 17−1 = 12 since 17 · 12 mod 29 = 1 //can't understand how this happen
17⋅12=1+7⋅29≡1 (mod 29) ⇒ 17−1≡12 (mod 29) explain this also
Best Answer
Below are a couple of ways to compute $\rm\: 17^{-1}\pmod{29}.\ $ First, twiddling fractions
$$\rm mod\ 29\!:\ \ \ {{\ \ \, 1\,\equiv\ \ \ 30}\atop{17\,\equiv\, -12}}\ \ \ \Rightarrow\ \ \ \frac{1}{17}\ \equiv\ \frac{\ 30\ }{-12\ }\ \equiv\ \frac{5}{-2\ }\,\equiv\,\frac{-5\,}2\,\equiv\,\frac{24}2\,\equiv\,12$$
Alternatively, mechanically applying the Extended Euclidean Algorithm
$$\begin{eqnarray} 29 &\ =\ &\ \ \ 1&\cdot& 29 &+&\ 0&\cdot& 17\\ 17 &=&\ \ \ 0&\cdot& 29 &+&\ 1&\cdot& 17\\ 12 &=&\ \ \ 1&\cdot& 29 &-&\ 1&\cdot& 17\\ 5 &=& -1&\cdot &29 &+&\ 2&\cdot& 17\\ 2 &=&\ \ \ 3&\cdot& 29 &-&\ 5&\cdot& 17\\ 1 &=& -7&\cdot& 29 &+& 12&\cdot& 17\end{eqnarray}$$
Hence the final equation implies that $\rm\: 12\cdot 17\equiv 1\pmod{29}$