I have questions on the integer factorization algorithm described on Wiki. The Wiki description is heavy English and I translated it so it's more symbolic. My question is if this translation makes sense and follows in a bold questions section.
Wiki says for finding a divisor such that $(mod(a,b) = 0) \land a, b \in \mathbb{Z}$ an algorithm is followed. The repeated application of the algorithm to $b$ and $d = \frac a b$ gives the complete factorization of $a$ or decides if $a$ is prime.
It states in summary that the algorithm should only test $B_{test} = \{b \in \mathbb{Z} : 1 \lt b \land b^2 \le a\}$. The claim is that if there is a divisor $d$ such that form (1):
$((mod(a,d) = 0) \land (d^2 > a) \land d \in \mathbb{Z}) \implies (b = \frac a d \land (mod(a, b)=0) \land(b^2 \le a))$
Wiki states that if $b$ is tested in increasing order the first divisor $b$ is a prime number and for the cofactor $d$ this form (2) holds $((d = \frac a b) \land (mod(d,z) = 0) \land (d^2 \gt a) \land (d,z \in \mathbb{Z}))\implies (z \ge b)$. This part is confusing and I will explain in questions. For complete factorization, the algorithm is continued finding form (3) $(mod(d, b_2) = 0) \land (d \ge b) \land (d \ge \sqrt r)$. Finally, as an optimization, only prime values for $b$ need be tested using a generated table from a sieve.
QUESTIONS
- Is this an accurate description of the general algorithm? Appreciate guidance.
- Is Form (2) correct? I tested it on a number and it was false.
- Is there additional algebra proving $b^2 \le a$?
- I provide the following examples for repeated application. Are they accurate?
For example the recursive factorization algorithm $F(a, 1)$:
$ F(a, b)= \begin{cases} (),& \text{if } b^2\gt a\\ (b, \frac a b, F(a, b + 1)),& \text{if } mod(a,b) = 0 \\ F(a, b + 1), & \text{otherwise } \\ \end{cases} $
$ F(a, b)= \begin{cases} (),& \text{if } b \gt a\\ (b, F(a, b + 1)),& \text{if } mod(a,b) = 0 \\ F(a, b + 1), & \text{otherwise } \\ \end{cases} $
For example just prime factorization $P(a, 2)$:
$ P(a, b)= \begin{cases} (a),& \text{if } b^2\gt a\\ (b, P(\frac a b, b)),& \text{if } mod(a,b) = 0 \\ P(b + 1, \frac a b), & \text{otherwise } \\ \end{cases} $