Content deleted Content added
Line 23:
5. Stop computing terms of <math>\{y_i\}</math> and <math>\{d_i\}</math> when either of the following conditions are met:
:A) <math>y_j = x_N</math> for some <math>j</math>. If the sequences <math>\{x_i\}</math> and <math>\{y_j\}</math> "collide" in this manner, then we have:
::<math>x_N = y_j \Rightarrow \alpha^{b+d} = \beta\alpha^{d_j} \Rightarrow \beta = \alpha^{b+d-d_j} \Rightarrow x \equiv b+d-d_j \pmod{p}</math>
:and so we are done.
:B) <math>d_i > b-a+d</math>. If this occurs, then the algorithm has failed to find <math>x</math>. Subsequent attempts can be made by changing the choice of <math>S</math> and/or <math>f</math>.
==Complexity==
| |||