In the notes where I'm studying from there is written: "Let $G=\langle g\rangle$ be a subgroup of $(\mathbb{F}_{607}^*,\cdot)$ with $g=64$ and order $n=101$" but that felt strange to me; since I know that every subgroup of another group must have an order which divides the order of the group (Lagrange's theorem), but $607$ is prime. Is there an error in my notes so?
Anyway given $95 \in G$ I've to calculate the inverse: $95^{-1}$
Since the order of $G$ is prime ($101$), I know that every element in $G$ generates $G$, moreover each one of its elements will have an order dividing $|G|$, Consequently:
$$\forall x \in G \ \ \ x^{|G|} = 1 \pmod {|G|}$$
and so:
$$ x^{-1} = x^{|G|-1} \pmod {|G|}$$
so I applied
$$ 95^{-1} = 95^{100} \pmod {101}$$
To handle powers I rewrited it like:
$$95^{100} = (((95)^4)^5)^5 = ((84)^5)^5 = 1^5 = 1$$
But I was expecting to find $95^{-1}$
Could you please tell me where I'm doing wrong and if there are some errors in my notes?
I think I need to clarify the whole stuff.
The full description of the exercise is: "Let $G=\langle g\rangle$ be a subgroup of $(\mathbb{F}_{607}^*,\cdot)$ with $g=64$ and order $n=101$. Consider $h=122 \in G$, find $\log_g h \pmod n$ i.e. $x$ s.t. $h = g^x \Leftarrow\Rightarrow 122 = 64^x \pmod {101}$"
basically is an example on how to apply the "Pollard's $\rho$" algorithm.
at the end of the algorithm I encountered the fraction:
$x = \frac {64}{6} \pmod {101}$ but I think it's a typo and the correct result is:
$$x = \frac {64}{-6} \pmod {101}$$
because num and den are calculated through the differences $64-0$ (num) and $6-12$ (den).
To handle the fraction I thought to multiply the numerator by the inverse of the denominator, so:
$$x = 64 \cdot (-6)^{-1} \pmod {101}$$
But $-6 = 95 \pmod {101}$, hence I thought I needed to find the inverse of $95$ module $101$: $95^{-1} \pmod {101}$
So is $84$ the number I'm searching for?
So here is my attempt: You are looking at the multiplicative group $G$ generated by $64 \in \mathbb{F}_{607}^*$ i.e. the group of elements
$$ 64,64^2,64^3,\ldots $$
This group is of order $101$ and since $95 \in \mathbb{F}_{607}^*$ has order $202$ the only way of making sense out of $95 \in G$ is to interpret it as $64^{95} \in G$.
But now you are looking for a element $g \in G$ with $g*64^{95}=1 \in G$ i.e. you are looking for a number $m$ with $64^m*64^{95}=1 \in G$ but you already know that $64^{101}=1\in G$ and therefore $64^m*64^{95}=64^{m+95}=64^{101}=1 \in G$ and therefore $m=6$. This means (to follow the notation in your problem) that $6 \in G$ is the inverse of $95$.
Or in other words $64^6$ is the inverse of $64^{95}$ in $G$.