Using Pollards rho algorithm for logarithms

Question

I have been reading about the Pollard's rho algorithm for logarithms on Wikipedia.

I wanted to work out an example. I use $n = 16$ and $p=16$ in my working. (Not sure if this is correct) Further I use the primes $3$ and $13$.

I think I want to solve the congruence:

$$3^{\gamma}\equiv 13 \pmod{16}$$

I let ;

$$S_0={3^2,3^5,3^8,3^{11},3^{14}}$$ $$S_1={3^0,3^3,3^6,3^9,3^{12},3^{15}}$$ $$S_2={3^1,3^4,3^7,3^{10},3^{13}}$$

Then I get $a_1=0 \mod 16$, $b_1=0 \mod 16$, $x_1=1$, $x_{21}=1$, $a_{21}=0 \mod 16$, $b_{21}=0 \mod 16$

The value I get for $r$ is then;

$$r = 0 \mod 16$$ However this is = 0, so a failure result is obtained.

1) Is there a mistake in my working, or an incorrect interpretation of the algorithm?

Then presuming a non-zero $r$, I have to work out the multiplicative inverse of $r$

2) I know one can use Euclid's Algorithm for finding multiplicative inverses. How can use this to work out this multiplicative inverse?

Answer 1

For your second question, one can use the Euclidean algorithm to find the multiplicative inverse if there exists one.

Recall that some $a$ is invertible modulo $n$ if and only if $\gcd(a,n)=1$.

If this the case, then there exists $x,y$ such that $ax + ny = 1$. This $x$ is the inverse of $a$ modulo $n$. You find these $x,y$ by the extended Euclidean algorithm (keyword Bézout coefficients).

In general you can find $x,y$ such that $ax + ny = \gcd(a,n)$. Yet if the right hand side is not $1$ this gives no inverse. (And $\gcd(a,n)$ is the smallest positive integer such that $aX + nY = c$ has a solution; so if it's not $1$, then you cannot find an inverse for it does not exist.)

Thus in your case you cannot find an inverse.

---

For your first question, indeed the algorithm is such that it does not guarantee a solution for every starting value. Note that it contains the possibility of outputting "failure."

In this case you need to run the algorithm anew, with different starting values for $a_0,b_0,x_0$ (but be careful to compute the $x_0$ that matches the starting value $a_0,b_0$). Or, you change the sets $S_i$.

For computing by hand this is also an option but in general one will change the starting values not the $S_i$.

Some further remarks:

When you compute the discrete logarithm of $13$ to base $3$ in a cyclic group of order $16$ (the $p$), then you do this in the group "the multiplicative group of integers modulo $17$."

Thus you are looking for a solution to $$3^{\gamma} \equiv 13 \pmod{17}$$ so this congruence is modulo $17$ not $16$. Thus, the sets $S_0,S_1, S_2$ are also modulo $17$.

However the definition of the functions $g$ and $h$ in the proof you mention are modulo the order of the group, so indeed $16$.

Thus you need to do some calculations modulo $17$ and some others modulo $16$.

On the "failure." Your choice of sets and initial values is such that you will always get a failure. The problem is that your starting values $a_0,b_0$ are $0$ and your $x_0=1$ is in $S_1$ where the $a_i,b_i$ are not changed. Thus the stay the same, which is not desirable. The starting values $a_0,b_0$ are $0$ are common, what is not common is to have $1$ in $S_1$. You can read this in more detail in Section 3.6.3 of Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (2001). "Chapter 3" Handbook of Applied Cryptography, which is linked on the Wikipedia page you mentioned.

Answer 2

[Note the question has been heavily revised since this answer was written. Originally it asked only how to use Euclid's algorithm to invert $-32\,$ modulo $\,16$]

Mod $\,m,\ $ if $\ 0\,$ has an inverse $\,0^{-1}$ then $\,1 \equiv 00^{-1} \equiv 0\ $ so $\ m\mid 1\!-\!0 = 1,\ $ therefore $\ m = 1.\,$ This implies that every integer $\,n\equiv 0\,$ since $\, n\equiv n\cdot 1\equiv n\cdot 0 \equiv 0.\,$ Thus $\,0\,$ is invertible only in the degenerate case when the modulus $= 1$, i.e. only in a trivial one element ring $\,\Bbb Z_1 = \{0\}.$

Note $\,\ a\,$ is invertible $\iff a\mid 1\,\pmod m\iff ax\equiv 1\pmod m\,$ for some integer $\,x$

Let's consider more generally all multiples $\,x\,$ of $\,a\,$ mod $\,m.\,$ We have

$\begin{align} a\mid x\!\! \pmod m&\iff x \equiv aj\!\! \pmod m\ \ \ {\rm for\ some\ integer\ } j\\ &\iff x = aj + mk\quad\ \ {\rm for\ some\ integers\ } j,k\end{align}$

By Bezout we know the set $\, a\Bbb Z + m\Bbb Z = d\Bbb Z\ $ for $\, d =\gcd(a,m)$

Therefore $\ a\mid x\pmod m\iff \gcd(a,m)\mid x$

Therefore $\ a\mid 1\pmod m\iff \gcd(a,m)\mid 1\ \iff \gcd(a,m) = 1$

i.e. $\,\ a\,$ is invertible mod $\,m\iff a\,$ is coprime to $\,m.$