In the context of cryptography, I need to find the private key of a message and I need to use modular arithmetic. I understand how modular arithmetic using a clock with whole numbers. But I get really stuck when I get to fractions, for example:
1/3 mod 8
How do I find a modular of a fraction? Is there a method for finding this?
Thanks in advance!
On
Writing fractions like $\frac{1}{3} \pmod{8}$ is the same as writing $3^{-1} \pmod{8}$ which is the inverse of $3$ modulo $8$.
In other words, when you write $\frac{a}{b} \pmod{n}$ you're referring to a number $k$ such that $bk \equiv a \pmod {n}$ but you should pay attention that this fraction is defined if and only if $\gcd(b,n)=1$. In other words, the denominator must be relatively prime to the modulus.
To find what number modulo $n$ this fraction represents, you need to evaluate $b^{-1}$. You can do that by using the Euclidean algorithm to solve the Bézout equation $bx + ny = 1$. The $x$ in this equation will give you $b^{-1}$. If you know the factorization of $n$ you can also use Euler's totient function by noting that $b^{-1} \equiv b^{\varphi(n)-1} \pmod{n}$. After you know what $b^{-1}$ is you will see that $k \equiv a \dot b^{-1} \pmod {n}$.
The important property of $1/3$ is that $1/3 \cdot 3 = 1$. So, what number, when multiplied by $3$, is $1$ mod $8$?
Showing when $x^{-1} \pmod n$ exists and that it is unique is not too terrible either
EDIT: I didn't see "finding it". Check out the Extended Euclidian algorithm.