Pollard's \(\rho\) method

Section 6.4 Pollard's \(\rho\) method

We now look at a specific implementation of the Pollard \(\rho\) method for solving the discrete log problem \(g^t = h \mod p\) in \(\F_p\ad\text{.}\) Our first tool is a function that does a good job of mixing values through \(\F_p\text{.}\) For a prime \(p\text{,}\) let \(f:\F_p \to \F_p\) be the function

\begin{equation} f(x) = \left\{ \begin{array}{lll} gx \amp \mbox{if } \amp 1 \leq x \lt p/3 \\ x^2 \amp \mbox{if } \amp p/3 \leq x \lt 2p/3 \\ xh \amp \mbox{if } \amp 2p/3 \leq x \lt p \\ \end{array} \right.\label{eqn-pollard-f}\tag{6.4.1} \end{equation}

Following the abstract version of the rho method, we'll need two “lists” (remember, we're only storing one element at a time) to keep track of \(x_i\) and \(x_{2i}\) to find a collision. But we also need to keep track of what operations \(f\) has performed as we walk up the rho to find the collision. Since we can't predict what \(f\) will do, we will need counters that keep track of how many copies of \(g\) and \(h\) have been multiplied in by \(f\text{.}\) Note that because we're in \(\F_p\text{,}\) we need only to keep track of these exponents modulo \(p-1\) by Fermat's little theorem.

Suppose that we apply \(f\) a total of \(n\) times to the starting point \(x_0 = 1\text{.}\) Then

\begin{equation*} f\circ f \circ f \circ \ldots \circ f \circ f (1) = g^{a_n} h^{b_n} \end{equation*}

We can generate the “storage constants” as we calculate the list with the conditions

\begin{equation} a_n = \left\{ \begin{array}{lll} a_{n-1} +1 \amp \mbox{if } \amp 1 \leq x \lt p/3 \\ 2a_{n-1} \amp \mbox{if } \amp p/3 \leq x \lt 2p/3 \\ a_{n-1} \amp \mbox{if } \amp 2p/3 \leq x \lt p \\ \end{array} \right.\label{eqn-pollard-a}\tag{6.4.2} \end{equation}

and

\begin{equation} b_n = \left\{ \begin{array}{lll} b_{n-1} \amp \mbox{if } \amp 1 \leq x \lt p/3 \\ 2b_{n-1} \amp \mbox{if } \amp p/3 \leq x \lt 2p/3 \\ b_{n-1} +1 \amp \mbox{if } \amp 2p/3 \leq x \lt p \\ \end{array} \right.\label{eqn-pollard-b}\tag{6.4.3} \end{equation}

Consider the collision generating sequences

\begin{equation*} x_{i+1} = f(x_i) \mbox{ and } y_{i+1} = f(f(y_i)) \end{equation*}

with \(x_0 = 1\) and \(y_0 = f(1)\text{.}\) At the termination of the search for a collision, we'll have \(x_i = x_{2i}\text{.}\) That is, we'll have the equation

\begin{equation*} g^{a_1} h^{b_1} = g^{a_2} h^{b_2} \bmod p\text{.} \end{equation*}

Rearranging this, we get

\begin{equation*} g^{a_1 - a_2} = h^{b_2 - b_1} \bmod p \end{equation*}

which we can simplify by letting \(u = a_1 - a_2\) and \(v = b_2 - b_1\) to get

\begin{equation*} g^u = h^v \bmod p. \end{equation*}

Note that this is equivalent to the equation

\begin{equation*} v \cdot \log_g(h) = vt = u \bmod (p-1) \end{equation*}

where we mod by \(p-1\) because we've changed to an exponent equation in \(\F_p\text{.}\) If \(\gcd(v, p-1) = 1\text{,}\) then \(v\) has an inverse, and we can use that to solve for \(\log_g(h)\text{.}\) Otherwise, an application of the extended Euclidean algorithm to the numbers \(v\) and \(p-1\) will give an integer \(s\) so that

\begin{equation*} s v = d \bmod (p-1) \end{equation*}

where \(d = \gcd(v, p-1)\text{.}\) Multiplying through by \(s\text{,}\) we get

\begin{equation} d t = w \bmod (p-1)\label{eq-rho-solve}\tag{6.4.4} \end{equation}

with \(w = su\text{.}\)

An easy argument shows that since \(d | (p-1)\text{,}\) it must also be the case that \(d |w\text{.}\) Thus, it is immediately apparent that \(t = w/d\) is a solution to equation (6.4.4). But there are others. Since the equation holds modulo \(p-1\text{,}\) the complete set of solutions is given by

\begin{equation*} t = \left\{ \frac{w}{d} + k \frac{p-1}{d} : k = 0, \ldots d-1 \right\}. \end{equation*}

What is left is to try each of these potential solutions to

\begin{equation*} g^t = h \bmod p \end{equation*}

and find the correct exponent. In practice, the number \(d\) will be small, as to be cryptographically secure, \(p\) is chosen so that \(p-1\) has one very large prime factor that is unlikely to divide \(d\text{.}\)

Algorithm 6.4.1. Pollard's rho method for \(\F_p\).

\(g^t = h \bmod p\)

Initialize constants \(a_x, b_x, a_y, b_y = 0\text{.}\)
Intialize the list elements \(x = 1, y = 0\text{.}\)
Define the mixing function \(f\) by (6.4.1).
Set \(x = f(x), y = f(f(x))\text{,}\) and update the storage constants according to (6.4.2) and (6.4.3).
If \(x \neq y\text{,}\) repeat from Step 4.
Once a collision is found, set \(u = a_x - a_y\text{,}\) and \(v = b_y - b_x\text{.}\)
Apply the Euclidean algorith to \(v, p-1\) to get \(s, d\) so that \(s v = d \bmod p-1\) and \(d = \gcd(v, p-1)\text{.}\)
Set \(w = su\)
For \(k = 1, \ldots, d-1\text{,}\) calculate
\begin{equation*} t = \frac{w}{d} + k \frac{p-1}{d} \end{equation*}
and check
\begin{equation*} g^t = h \bmod p \end{equation*}

Exercises Exercises

1.

\(d = \gcd(v, p-1)\)\(dt = w \bmod (p-1)\)\(d | w\)

2.

\(f\)

3.

\(\rho\)