Editing Dixon's factorization method (section)

== Step-by-step example : factorizing (''n'' = 84923) using Dixon's algorithm ==
This example is lifted directly from the LeetArxiv substack.<ref>Kibicho, Murage (2025). [https://leetarxiv.substack.com/p/hand-written-paper-implementation ''Hand-Written Paper Implementation'']: Asymptotically Fast Factorization of Integers.</ref> Credit is given to the original author.
* '''Initialization''':
** Define a list of numbers ''L'', ranging from 1 to 84923:  
::: <math>L = \{1, \dots, 84923\}</math>
:* Define a value ''v'', which is the smoothness factor:  
::: <math>v = 7</math>
:* Define a list ''P'' containing all the prime numbers less than or equal to ''v'':  
::: <math>P = {2, 3, 5, 7}</math>
:* Define ''B'' and ''Z'', two empty lists. ''B'' is a list of powers, while ''Z'' is a list of accepted integers:
::: <math>B = [ ]</math>
::: <math>Z = [ ]</math>
 
* '''Step 1''': Iterating <math>z</math> values 
** Write a for loop that indexes the list <math>L</math>. Each element in <math>L</math> is indexed as <math>z</math>. The for loop exits at the end of the list.  
::<syntaxhighlight lang="c">
int n = 84923;
for (int i = 1; i <= n; i++)
{
    int z = i;
}
</syntaxhighlight>
* '''Step 2''': Computing <math>z^2 \mod n</math> and v-smooth Prime Factorization 
** To proceed, compute <math>z^2 \mod 84923</math> for each ''z'', then express the result as a prime factorization.
:: <math>
1^2 \mod 84923 \equiv 1 \mod 84923 = 2^0 \cdot 3^0 \cdot 5^0 \cdot 7^0 \mod 84923
</math>
:: <math>
\vdots
</math>
:: <math>
513^2 \mod 84923 = 8400 \mod 84923 = 2^4 \cdot 3^1 \cdot 5^2 \cdot 7^1 \mod 84923
</math>
::<math>
\vdots
</math>
::<math>
537^2 \mod 84923 = 33600 \mod 84923 = 2^6 \cdot 3^1 \cdot 5^2 \cdot 7^1 \mod 84923
</math>
::<math>
538^2 \mod 84923 = 34675 \mod 84923 = 5^2 \cdot 19^1 \cdot 73^1 \mod 84923
</math>

::This step continues for all values of ''z'' in the range.

* '''Step 3''': If <math>z^2 \mod 84923</math> is ''7-smooth'', then append its powers to list <math>B</math> and append <math>z</math> to list <math>Z</math>.
::<math>Z = \{1, 513, 537\}</math>
::<math>B = \{ [0, 0, 0, 0], [4, 1, 2, 1], [6, 1, 2, 1] \}</math>

* '''Step 4''': This step is split into two parts.
:: '''Part 1''': Find <math>B</math> modulo 2.
::<math>
B =
\begin{pmatrix}
0 & 0 & 0 & 0 \\
4 & 1 & 2 & 1 \\
6 & 1 & 2 & 1
\end{pmatrix}
\mod 2
\equiv
B =
\begin{pmatrix}
0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 \\
0 & 1 & 0 & 1
\end{pmatrix}
</math>

:: '''Part 2''': Check if any row combinations of <math>B</math>  sum to even numbers

:::For example, summing Row <math>2</math> and Row <math>3</math> gives us a vector of even numbers.

:::<math>
R_2 = \{0, 1, 0, 1\}</math> and <math>R_3 = \{0, 1, 0, 1\}</math>

:::then 
:::<math>R_2 + R_3 = \{0, 1, 0, 1\} + \{0, 1, 0, 1\}</math>  
:::<math>R_2 + R_3 = \{0, 2, 0, 2\}</math>.


* '''Step 5''' : This step is split into four parts.
** '''Part 1. (Finding x)''': Multiply the corresponding <math>z</math> values for the rows found in '''Step 4'''. Then find the square root. This gives us <math>x</math>.  
*** For Row 2, we had <math>2^4 * 3^1 * 5^2 * 7^1</math>.  
*** For Row 3, we had <math>2^6 * 3^1 * 5^2 * 7^1</math>.  
*** Thus, we find <math>x</math> :

::::<math>
\begin{array}{ll}
(513 \cdot 537) ^ 2 \mod 84923 = y ^ 2 \\
\\
\text{where} \quad x^2 \mod 84923 = (513 \cdot 537) ^ 2 \mod 84923  \\
\\
\text{thus} \quad x = (513 \cdot 537) \mod 84923 \\
\\
\text{so} \quad x = 275481  \mod 84923\\
\\
\text{Finally} \quad x = 20712  \mod 84923\\
\end{array}
</math>

:* '''Part 2. (Finding y)''': Multiply the corresponding smooth factorizations for the rows found in '''Step 4'''. Then find the square root. This gives us <math>y</math>.  
:::<math>
\begin{array}{ll}
y^2 = (2^4 \cdot 3^1 \cdot 5^2 \cdot 7^1) \times (2^6 \cdot 3^1 \cdot 5^2 \cdot 7^1) \\  
\\
\text{By the multiplication law of exponents,} \\  
y^2 = 2^{(4+6)} \cdot 3^{(1+1)} \cdot 5^{(2+2)} \cdot 7^{(1+1)} \\ 
\\ 
\text{Thus,} \\  
y^2 = 2^{10} \cdot 3^2 \cdot 5^4 \cdot 7^2 \\  
\\
\text{Taking square roots on both sides gives} \\  
y = 2^5 \cdot 3^1 \cdot 5^2 \cdot 7^1 \\  
\\
\text{Therefore,} \\  
y = 32 \times 3 \times 25 \times 7 \\  
\\
\text{Finally,} \\  
y = 16800  
\end{array}
</math>

:* '''Part 3. (Find x + y and x - y)''' where ''x = 20712'' and ''y = 16800''.
::: <math>x + y = 20712 + 16800 = 37512</math>
::: <math>x - y = 20712 - 16800 = 3912</math>

:* '''Part 4. Compute GCD(x+y, n) and GCD(x-y, n),''' where ''n = 84923'', ''x+y = 292281'' and ''x-y = 258681''
  
:::<math>
\begin{array}{ll}
\gcd(37512, 84923) = 521 \\
\gcd(3912, 84923) = 163
\end{array}
</math>

Quick check shows <math>84923 = 521 \times 163</math>.