0
$\begingroup$

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

enter image description here

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?

$\endgroup$
3
  • $\begingroup$ You show this example, and then you ask about "not in this example"... Make up your mind. $\endgroup$ – fkraiem Nov 22 '17 at 10:34
  • $\begingroup$ What I mean is how did he get that rule. Is there a general explanation? $\endgroup$ – malloc Nov 22 '17 at 10:43
  • 1
    $\begingroup$ 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". $\endgroup$ – Lery Nov 22 '17 at 11:36
1
$\begingroup$

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)
1    228        0       2       228^2 mod 383 = 279
2    279        0       2       279^2 mod 383 = 92
3     92        2       3       2*92  mod 383 = 184
4    184        1       1     228*184 mod 383 = 205
5    205        1       1     228*205 mod 383 = 14
6     14        ...
$\endgroup$
2
  • $\begingroup$ I don't understand where he get x mod3. Is there a general explanation/rule? $\endgroup$ – malloc Nov 22 '17 at 11:29
  • 1
    $\begingroup$ 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. $\endgroup$ – gammatester Nov 22 '17 at 11:36

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.