Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
You'll get better answers if you say precisely why you don't understand that $$\rm 17\cdot 12 = 1 + 7\cdot 29\equiv 1\,\ (mod\ 29)\ \Rightarrow\ 17^{-1}\equiv 12\,\ (mod\ 29)$$ –  Bill Dubuque Sep 29 '12 at 19:26
    
oh,,,I can't understand this either, lets forget 12,,,then how we find inverse(17). (I am new to modular arithmatic in finite field maths)...can you give me a simple explanation please,,thanks –  user827918 Sep 29 '12 at 19:33
    
You can compute modular inverses by the extended Euclidean algorithm. –  Bill Dubuque Sep 29 '12 at 19:34
    
thanks very much, I really appreciate your help, but I can't understand these complex things, really sorry about that. could you please give me steps to find inverse of 17 in ff(29). I mean mathematical steps –  user827918 Sep 29 '12 at 19:41
    
I just added an answer. –  Bill Dubuque Sep 29 '12 at 20:16
add comment

1 Answer 1

up vote 1 down vote accepted

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}$

share|improve this answer
    
thanks a lot sir –  user827918 Sep 29 '12 at 20:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.