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?

  • 1
    $\begingroup$ The order of the multiplicative group of $\mathbb F_p$ is $p-1$, not $p$ (as $0$ has no inverse). $\endgroup$
    – lulu
    Jul 14 '16 at 21:44
  • $\begingroup$ 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 $\endgroup$
    – ela
    Jul 14 '16 at 21:46
  • $\begingroup$ 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. $\endgroup$
    – Maik Pickl
    Jul 14 '16 at 22:04
  • $\begingroup$ Lulu deleted his comment. You have that $a^{p-1}=1$ mod $ p$. Apply this in $\mathbb{F}_{607}$. $\endgroup$
    – Maik Pickl
    Jul 14 '16 at 22:08
  • $\begingroup$ 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.$ $\endgroup$
    – Doug M
    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.$$

  • $\begingroup$ That's much better. :) I delete my earlier comments to keep it clean. $\endgroup$
    – Maik Pickl
    Jul 14 '16 at 23:02
  • $\begingroup$ Once the problem phrasing has been cleared :o) $\endgroup$
    – Bernard
    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$.

  • $\begingroup$ I edited the question to make it clearer, take a look if you want =) $\endgroup$
    – ela
    Jul 14 '16 at 23:23
  • $\begingroup$ @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$. $\endgroup$
    – Maik Pickl
    Jul 14 '16 at 23:34
  • $\begingroup$ 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$? $\endgroup$
    – ela
    Jul 14 '16 at 23:39
  • $\begingroup$ @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. $\endgroup$
    – Maik Pickl
    Jul 14 '16 at 23:43
  • $\begingroup$ @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. $\endgroup$
    – Maik Pickl
    Jul 14 '16 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.