Karatsuba multiplication
Let $$ \begin{align} x & =x_1 B^m+x_0, \\ y & =y_1 B^m+y_0, \end{align} $$ where $x_0$ and $y_0$ are less than $B^m$. The product is then $$ \begin{align} xy & =(x_1 B^m+x_0 )(y_1 B^m+y_0 ) \\ & =x_1 y_1 B^{2m}+(x_1 y_0+x_0 y_1 ) B^m+x_0 y_0 \\ & =z_2 B^{2m}+z_1 B^m+z_0 \end{align} $$ where $$ \begin{align} z_2=x_1 y_1, \\ z_1=x_1 y_0+x_0 y_1, \\ z_0=x_0 y_0 \end{align} $$ and $$z_1=(x_1+x_0 )(y_1+y_0 )-z_2-z_0$$
Reversing Karatsuba multiplication for integer factoring
Let $n=xy$ where $x,y,n \in \mathbb{Z}$. Without loss of generality $x \le \sqrt n \le y$. If we choose $B^m \gt \sqrt n$ then $$ \begin{align} x & =x_1 B^m+x_0=0 \cdot B^m+x_0 = x_0, \\ y & =y_1 B^m+y_0=y_1 \cdot B^m+y_0. \end{align} $$
Therefore, $$ \begin{align} z_2 & =0, \\ \therefore z_1 & =(x_1+x_0 )(y_1+y_0 )-z_2-z_0 \\ & =(0+x_0 )(y_1+y_0 )-0-z_0 \\ & =x_0 (y_1+y_0 )-z_0 \\ & =x_0 y_1. \end{align} $$ Therefore, $$ \begin{align} n=xy & =z_2 B^{2m}+z_1 B^m+z_0 \\ & =0 \cdot B^{2m}+x_0 y_1 \cdot B^m+x_0 y_0 \\ & =x_0 y_1 B^m+x_0 y_0 \\ & =n_1 B^m+n_0 \\ \end{align} $$
We have $$ n=B^m (n_1)+1(n_0) $$
This may be treated as a linear Diophantine equation $$n=B^m \cdot X+1 \cdot Y$$ with an initial solution $(X_0,Y_0 )=(n_1,n_0)$. All solutions are given by $$ \begin{align} X & =X_0-t=n_1-t, \\ Y & =Y_0+B^m t=n_0+B^m t. \end{align} $$
For some integer $t$, we have $\gcd{(n_0+B^m t,n)}$ yielding a non-trivial divisor of $n$. We may view $t$ as the "carry" from the multiplication of the least significant "digits", $x_0 y_0$.
Example: Let $$ \begin{align} n & =2263 = 31 \times 73 \text{ (Let's check...)}\\ \lfloor \sqrt{n} \rfloor & =47 \end{align} $$
$7^2$ is the nearest power. So $B^m=7^2$.
$$ \begin{align} n & =46 \times 7^2+9 \\ n_1 & =46,n_0=9 \\ \gcd(9,2263) & =1 \\ \gcd(9+49,2263) & = \gcd(56,2263)=1 \\ \cdots \\ \gcd(9+15 \times 49,2263) & = \gcd(744,2263)=31 \\ \end{align} $$
It took 16 trials and GCD computations to find the smaller factor and 16 is around half of the smaller factor, which is about the same complexity as trial division (since we can just check odd numbers upto $\sqrt{n}$).
We observe that $8^2 = 64$ is also a perfect square and lies between the smaller and larger cofactors of $2263$ i.e., $31 \le 8^2 \le 73$
$$ \begin{align} n & =35 \times 8^2+23 \\ n_1 & =35,n_0=23 \\ \gcd(23,2263) & =1 \\ \gcd(23+64,2263) & = 1 \\ \cdots \\ \gcd(23+4 \times 64,2263) & =31 \\ \end{align} $$
It took only 4 trials with $B^m = 8^2$.
Lets try $2^5 = 32$. This is still a perfect power that lies between the two cofactors $31$ and $73$.
$$ \begin{align} n & =70\times32+23 \\ \gcd(23,2263) & =1 \\ \gcd(23+32,2263) & = 1 \\ \cdots \\ \gcd(23+8 \times 32,2263) & = 31 \\ \end{align} $$ We find $31$ as a non-trivial factor in 9 trials.
When we try $B^m = 9^2$ which is a power greater than the larger cofactor $73$, we get the cofactor in $59$ trials (using $\gcd(76 + 58*9^2,2263)$).
When we try $B^m = 2^4 = 16$ which is smaller than the smallest cofactor $31$, we get the cofactor in 18 trials (using $\gcd(7 + 17*2^4,2263)$).
Questions:
- If we choose a perfect power between the smaller and larger cofactors, it makes the $x_1$ term 0 in the Karatsuba multiplication. The gcd trick works because we are reversing the effect of the carry from the product of least significant "digits" ($x_0 y_0$) as shown below. Is there a way for us to choose the "optimal" perfect power $B^m$? For eg: $8^2$ that yielded in 4 trials.
$$ \begin{align} n=xy & =z_2 B^{2m}+z_1 B^m+z_0 \\ & =0 \cdot B^{2m}+x_0 y_1 \cdot B^m+x_0 y_0 \end{align} $$