Skip to content

Commit 5acf2fb

Browse files
committed
Update factorization.md
begin to cycle -> converge into a loop
1 parent 0dad30c commit 5acf2fb

File tree

1 file changed

+1
-1
lines changed

1 file changed

+1
-1
lines changed

src/algebra/factorization.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -239,7 +239,7 @@ The algorithm looks at a pseudo-random sequence $\{x_i\} = \{x_0,~f(x_0),~f(f(x_
239239

240240
In this instance, we are not interested in the sequence $\{x_i\}$.
241241
We are more interested in the sequence $\{x_i \bmod p\}$.
242-
Since $f$ is a polynomial function, and all the values are in the range $[0;~p)$, this sequence will eventually begin to cycle.
242+
Since $f$ is a polynomial function, and all the values are in the range $[0;~p)$, this sequence will eventually converge into a loop.
243243
The **birthday paradox** actually suggests that the expected number of elements is $O(\sqrt{p})$ until the repetition starts.
244244
If $p$ is smaller than $\sqrt{n}$, the repetition will likely start in $O(\sqrt[4]{n})$.
245245

0 commit comments

Comments
 (0)