Calculating Decimal points of modulo operations

186 Views Asked by At

I am not too sure of the step that has occurred here (I found this form a cryptography book but I do not understand how he finds the second 9).

The function found in the image is $(2 \cdot 1)^{-1}(3 \cdot 5^2 + 2) = 2^{-1} \cdot 9 \equiv 9 \cdot 9 \equiv 13\,\mod\,17$

My calculations are that: $(2 \cdot 1)^{-1}(3 \cdot 5^2 + 2) = 2^{-1} \cdot 9 = 4.5 \not\equiv 9 \cdot 9 \equiv 13\,\mod\,17$

Equation from Book

3

There are 3 best solutions below

1
On BEST ANSWER

How he finds the second $9$:

$2^{-1}\equiv9\pmod{17}$ because $9\cdot2=18\equiv1\pmod{17}$

4
On

The ${^{-1}}$ is for modular multiplicative inverse, not reciprocal. Even if you treat it that way: $$4+2^{-1}=4+{1\over 2}\equiv 4+{18\over 2}=4+9=13\pmod {17}$$ in this case.

0
On

In modulo arithimetic then expression $(2^{-1})$ does not mean $0.5$ which is completely out of the purview of modular arithmetic (which is about equivalence classes of integers).

Instead $(2^{-1})$ refers to the the solution to $2x \equiv 1\pmod n$

And $2x \equiv 1 \pmod {17}\iff x \equiv 9 \pmod {17}$[1]

So $2^{-1}\equiv 9 \pmod {17}$.

======

[1] $2x \equiv 1 \pmod {17} \implies \exists k\in \mathbb Z$ so that $2x = 1 + 17k$ so $2|1+17k$ but $2\not \mid 1$ so $2\not \mid 17k$ so $k$ is odd. If $k = 2m + 1$ then $2x = 1 + (2m+1)17 = 18 + 34m$ which means $x = 9 + 17m$ or $x \equiv 9 \pmod {17}$ is the only solution ($\pmod {17}$).