8000 Update src/algebra/factorization.md · cp-algorithms/cp-algorithms@2597e05 · GitHub
[go: up one dir, main page]

Skip to content

Commit 2597e05

Browse files
t0wbo2tadamant-pwn
andauthored
Update src/algebra/factorization.md
Co-authored-by: Oleksandr Kulkov <adamant.pwn@gmail.com>
1 parent 997afa0 commit 2597e05

File tree

1 file changed

+2
-2
lines changed

1 file changed

+2
-2
lines changed

src/algebra/factorization.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -188,8 +188,8 @@ Notice, if $p-1$ divides $M$ for all prime factors $p$ of $n$, then $\gcd(a^M -
188188
In this case we don't receive a factor.
189189
Therefore, we will try to perform the $\gcd$ multiple times, while we compute $M$.
190190
191-
Some composite numbers don't have $\mathrm{B}$-powersmooth factors for small $\mathrm{B}$.
192-
For example, the factors of the composite number $100~000~000~000~000~493 = 763~013 \cdot 131~059~365~961$ are $190~753$-powersmooth and $1~092~161~383$-powersmooth.
191+
Some composite numbers don't have factors $p$ s.t. $p-1$ is $\mathrm{B}$-powersmooth for small $\mathrm{B}$.
192+
For example, for the composite number $100~000~000~000~000~493 = 763~013 \cdot 131~059~365~961$, values $p-1$ are $190~753$-powersmooth and $1~092~161~383$-powersmooth correspondingly.
193193
We will have to choose $B >= 190~753$ to factorize the number.
194194
195195
In the following implementation we start with $\mathrm{B} = 10$ and increase $\mathrm{B}$ after each each iteration.

0 commit comments

Comments
 (0)
0