# Calculate multiplicative inverse of $95$ in group of order $n=101$ which is subgroup of $(\mathbb{F}_{607}^*,\cdot)$

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?

• The order of the multiplicative group of $\mathbb F_p$ is $p-1$, not $p$ (as $0$ has no inverse).
– lulu
Jul 14 '16 at 21:44
• You're right, so this answers the first question... But I still don't get what is my mistake in the calculation of the inverse
– ela
Jul 14 '16 at 21:46
• The group $G$ is a red herring. The inverse in $G$ is the same as in $\mathbb{F}_{607}$. Apply this with what @lulu is writing. Jul 14 '16 at 22:04
• Lulu deleted his comment. You have that $a^{p-1}=1$ mod $p$. Apply this in $\mathbb{F}_{607}$. Jul 14 '16 at 22:08
• If $95$ is in $G$ then $95^{-1} \equiv 95^{100} \mod 607$...but, I am not so sure that $95$ is in $G.$ I have $95$ as a generator of a group order $202.$ Jul 14 '16 at 22:17

Since $64^{101}\equiv 1\mod 607$, the inverse of $64^{95}$ is $$64^6=2^{36}=512^4\equiv(-95)^4\equiv(527)^2\equiv(-80)^2\equiv 6400\equiv 330\mod 607.$$

• That's much better. :) I delete my earlier comments to keep it clean. Jul 14 '16 at 23:02
• Once the problem phrasing has been cleared :o) Jul 14 '16 at 23:04

First, write $\;95=5\cdot19\;$ , and now

$$607\cdot2=1214\implies 1215\div5=243\implies 5^{-1}=243\pmod{607}$$

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

• I edited the question to make it clearer, take a look if you want =)
– ela
Jul 14 '16 at 23:23
• @AlessioMartorana You are killing me. :) That is a completly different question now, First of all you are looking for $122=64^x$ mod $607$ not mod $101$. Then $64/6$ is indeed the right fraction not $64/-6$. No you are looking for the inverse of $6$ mod $101$ which is $6^{99}=17$ mod $101$. Jul 14 '16 at 23:34
• Mmh that's strange... 1. The $122=64^x \pmod{101}$ comes directly from the notes, I didn't add nothinng ^^. 2. Why $64/6$ is the right fraction if the difference at den is $6-12 = -6$?
– ela
Jul 14 '16 at 23:39
• @AlessioMartorana I don't know about your notes but why would you want to look for $64^x=122$ mod $101$ if $64$ is an element in $\mathbb{F}_{607}^*$ and $122$ is bigger than $101$? This doesn't make sense at all. Secondly I don't know how your algorithm arrives at the conclusion but you have that $64^{17*64}=122$ mod $607$ which gives me confidence that this is indeed the right solution. Jul 14 '16 at 23:43
• @AlessioMartorana You are looking for $122 \in G$. In $G$ the elements are of the form $64^x$ mod $607$. So you are looking for a number $x$ with $122=64^x$ mod $607$. Looking mod $101$ doesn't make sense. Jul 14 '16 at 23:48