You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
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$ withprime 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$ andlet $p$ be a prime such that $(p - 1)\geqslant 1$. Suppose theprime factorizationof $(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}$.
164
164
E.g. the prime factorization of $4817191$ is $1303 \cdot 3697$.
165
165
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$.
166
166
In 1974 John Pollard invented a method to extracts $B$-powersmooth factors from a composite number.