Can you help me understand Pollard's rho example?

I'm studying the Pollard's rho algorithm to solve discrete logaritms on the Handbook of applied cryptografy but I didn't understand one part of the theory and looking at the example gets me more confused.

This is the example

The first thing that I don't understand is how do you know that an element is on $$S_1$$ or $$S_2$$ or $$S_3$$ (in general not in in this example because is explained)and the second thing is: where did he get mod 3?

• You show this example, and then you ask about "not in this example"... Make up your mind. Nov 22, 2017 at 10:34
• What I mean is how did he get that rule. Is there a general explanation? Nov 22, 2017 at 10:43
• Using $\bmod n$ is a convenient way to partition your elements into $n$ subsets, it's just like "assigning a number between 1 and $n$ to each participants so that the participants can form $n$ groups".
– Lery
Nov 22, 2017 at 11:36

The algorithm is clear about all your questions. The partitions of $G=\mathbb{Z}^{*}_{383}$ are the sets $$S_1=\{x \in G: x \bmod 3=1\}$$ $$S_2=\{x \in G: x \bmod 3=0\}$$ $$S_3=\{x \in G: x \bmod 3=2\}$$ Here are the left parts ($x_i$) of the computation slightly more detailed with $x_i \bmod 3$ and the corresponding sets $S_k$
i    x_i    x_i mod 3  S_k          x_(i+1)

• This comes from the 'partition in roughly equal sizes'. This is obvious with the $\bmod 3$ definition. You can choose other partitions, e.g. $S_1$ is the set $x < \lfloor p/3\rfloor$, $S_3$ is the set $x \ge \lfloor 2p/3\rfloor$, and $S_2$ are the remaining values. Nov 22, 2017 at 11:36