8000 Update factorization.md [Update powersmooth definition with suggestions] · cp-algorithms/cp-algorithms@422fb19 · GitHub
[go: up one dir, main page]

Skip to content

Commit 422fb19

Browse files
authored
Update factorization.md [Update powersmooth definition with suggestions]
Commas are now outside $...$ and definiton is for (p - 1) for consistency.
1 parent 27e90b5 commit 422fb19

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
@@ -160,7 +160,7 @@ By looking at the squares $a^2$ modulo a fixed small number, it can be observed
160160
## Pollard's $p - 1$ method { data-toc-label="Pollard's <script type='math/tex'>p - 1</script> method" }
161161
162162
It is very likely that at least one factor of a number is $B$**-powersmooth** for small $B$.
163-
$B$-powersmooth means that every prime power $d^k$ that divides $p-1$ is at most $B$. Formally, let $\mathrm{B} \geqslant 1$ and $n \geqslant 1$ with prime factorization $n = \prod {p_i}^{e_i},$ then $n$ is $\mathrm{B}$-powersmooth if, for all $i,$ ${p_i}^{e_i} \leqslant \mathrm{B}$.
163+
$B$-powersmooth means that every prime power $d^k$ that divides $p-1$ is at most $B$. Formally, let $\mathrm{B} \geqslant 1$ and let $p$ be a prime such that $(p - 1) \geqslant 1$. Suppose the prime factorization of $(p - 1)$ is $(p - 1) = \prod {q_i}^{e_i}$, where each $q_i$ is a prime and $e_i \geqslant 1$ then $(p - 1)$ is $\mathrm{B}$-powersmooth if, for all $i$, ${q_i}^{e_i} \leqslant \mathrm{B}$.
164164
E.g. the prime factorization of $4817191$ is $1303 \cdot 3697$.
165165
And the factors are $31$-powersmooth and $16$-powersmooth respectably, because $1303 - 1 = 2 \cdot 3 \cdot 7 \cdot 31$ and $3697 - 1 = 2^4 \cdot 3 \cdot 7 \cdot 11$.
166166
In 1974 John Pollard invented a method to extracts $B$-powersmooth factors from a composite number.

0 commit comments

Comments
 (0)
0