Nothing is more frustrating than a book example that doesn't seem to make sense. I have been tasked to make an elliptical encryption accelerator, and it seemed prudent to read a book on cryptography, so I am reading "Understanding Cryptography" by Paar and Pelzl. I have attached pages 244 and 245, and 245 has an example 9.4 that is worked out. My issue is s.
I have $s$, $$s=\frac{3x^2 + 2}{2y} \bmod p,$$ where $x=5$, $y=1$ and $p =17$ This results in $$s=\frac{3\cdot5^2 + 2}{2} \bmod 17 = \frac{75 + 2}{2} \bmod 17$$ My issue starts here with the simplification of s: $$s=\frac{7 + 2}{2} \bmod 17$$
I get $9/2$.
The book result is $$2^{-1} \cdot 9 = 9 \cdot 9 = 13 \bmod 17$$ How does $$2^{-1} \cdot 9$$ become $$9 \cdot 9.$$
Any guidance would be helpful as I just cannot get my head around that leap.
In modulo arithmetic, the inverse of a number $a$ modulo $n$ is defined as the number $b$ such that $$ab \equiv 1 \pmod{n}$$ This can be written as $b = \frac1a$, but is more commonly written as $b = a^{-1}$.
When $n$ is prime, every number has an inverse. For example, the inverse of 2 modulo 17 is 9 because their product is $18 \equiv 1 \pmod{17}$; but in modulo 12, 4 does not have an inverse. To learn more about inverses and modulo arithmetic, I guess basic group theory or intermediate number theory would do.