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$.
162
+
It is very likely that a number $n$ has at least one prime factor $p$ such that $p - 1$ is $\mathrm{B}$**-powersmooth** for small $\mathrm{B}$. An integer $m$ is said to be $\mathrm{B}$-powersmooth if every prime power dividing $m$ is at most $\mathrm{B}$. Formally, let $\mathrm{B} \geqslant 1$ and let $m$ be any positive integer. Suppose the prime factorization of $m$ is $m = \prod {q_i}^{e_i}$, where each $q_i$ is a prime and $e_i \geqslant 1$. Then $m$ is $\mathrm{B}$-powersmooth if, for all $i$, ${q_i}^{e_i} \leqslant \mathrm{B}$.
164
163
E.g. the prime factorization of $4817191$ is $1303 \cdot 3697$.
165
-
And thefactorsare $31$-powersmooth and $16$-powersmoothrespectably, because $1303 - 1 = 2 \cdot 3 \cdot 7 \cdot 31$ and $3697 - 1 = 2^4 \cdot 3 \cdot 7 \cdot 11$.
166
-
In 1974 John Pollard invented a method toextracts $B$-powersmooth factors from a composite number.
164
+
And thevalues, $1303 - 1$ and $3697 - 1$,are $31$-powersmooth and $16$-powersmoothrespectively, because $1303 - 1 = 2 \cdot 3 \cdot 7 \cdot 31$ and $3697 - 1 = 2^4 \cdot 3 \cdot 7 \cdot 11$.
165
+
In 1974 John Pollard invented a method toextract factors $p$, s.t. $p-1$ is $\mathrm{B}$-powersmooth, from a composite number.
167
166
168
167
The idea comes from [Fermat's little theorem](phi-function.md#application).
169
168
Let a factorization of $n$ be $n = p \cdot q$.
@@ -180,7 +179,7 @@ This means that $a^M - 1 = p \cdot r$, and because of that also $p ~|~ \gcd(a^M
180
179
181
180
Therefore, if $p - 1$ for a factor $p$ of $n$ divides $M$, we can extract a factor using [Euclid's algorithm](euclid-algorithm.md).
182
181
183
-
It is clear, that the smallest $M$ that is a multiple of every $B$-powersmooth number is $\text{lcm}(1,~2~,3~,4~,~\dots,~B)$.
182
+
It is clear, that the smallest $M$ that is a multiple of every $\mathrm{B}$-powersmooth number is $\text{lcm}(1,~2~,3~,4~,~\dots,~B)$.
@@ -189,11 +188,11 @@ Notice, if $p-1$ divides $M$ for all prime factors $p$ of $n$, then $\gcd(a^M -
189
188
In this case we don't receive a factor.
190
189
Therefore, we will try to perform the $\gcd$ multiple times, while we compute $M$.
191
190
192
-
Some composite numbers don't have$B$-powersmoothfactorsfor small $B$.
193
-
For example,the factors ofthe 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.
194
-
We will have to choose $B>= 190~753$ to factorize the number.
191
+
Some composite numbers don't havefactors $p$ s.t. $p-1$ is $\mathrm{B}$-powersmooth for small $\mathrm{B}$.
192
+
For example,forthe 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.
193
+
We will have to choose $B\geq 190~753$ to factorize the number.
195
194
196
-
In the following implementation we start with $B = 10$ and increase $B$ after each each iteration.
195
+
In the following implementation we start with $\mathrm{B} = 10$ and increase $\mathrm{B}$ after each each iteration.