## Semiprime factorization and modular arithmetics

Edit 6.6.2016. Premature optimization is a source for errors. The following is completely wrong. Would like to smoke the same thing again. Linear algebra does not work here. We need characterization of quotient space. What I do not understand is why fast methods are working modulo number itself, but not other prime numbers.

Suppose we have number $N=xy$, where we know $N$ and want to find prime factors $x$ and $y$.

Lets take small prime $p$, than we can write $N= (x_p p + a_p)(y_p p + b_p)= (x_p y_p) p^2 + (b_p x_p + a_p y_p) p + a_p b_p$.

Step 0

One can observe that $a_p b_p= N \mod p$, since multiplication group modulo prime is cyclic for each $a_p \neq 0$ there is unique $b_p$ satisfying the equation. In other words we need to test $p-1$ values to find correct one, if we can. From now on I assume $a_p, b_p$ satisfy $a_p b_p= N \mod p$ and therefore $p$ divides $N- a_p b_p$.

Step 1

One can observe that $b_p x_p + a_p y_p = \frac{N- a_p b_p}{p} \mod p$, so we can write $x_p = -b_p^{-1} a_p y_p + b_p^{-1} \frac{N- a_p b_p}{p} \mod p$ since $b_p \neq 0$. In other words $\exists t_{p1} \in \mathbb{Z} | x_p = -b_p^{-1} a_p y_p + b_p^{-1} \frac{N- a_p b_p}{p}+t_{p1} p$. Substituting it into original equation we get $N - a_p b_p = (-b_p^{-1} a_p y_p + b_p^{-1} \frac{N- a_p b_p}{p}+t_{p1} p ) y_p p^2 + (b_p (-b_p^{-1} a_p y_p + b_p^{-1} \frac{N- a_p b_p}{p}+t_{p1} p ) + a_p y_p) p = t_{p1} y_p p^3 + (-b_p^{-1} a_p y_p^2 + b_p^{-1} \frac{N- a_p b_p}{p} y_p +b_p t_{p1} ) p^2 + N- a_p b_p$. Summarizing,
$x_p = -b_p^{-1} a_p y_p + b_p^{-1} \frac{N- a_p b_p}{p}+t_{p1} p$
$t_{p1} y_p p + (-b_p^{-1} a_p y_p^2 + b_p^{-1} \frac{N- a_p b_p}{p} y_p +b_p t_{p1} ) =0$.

Step 2
$t_{p1}= b_p^{-2} (a_p y_p^2 - b_p^{-1} \frac{N- a_p b_p}{p} y_p) +t_{p2} p, t_{p2} \in \mathbb{Z}$.
$x_p= -b_p^{-1} a_p y_p + b_p^{-1} \frac{N- a_p b_p}{p}+b_p^{-2} (a_p y_p^2 - b_p^{-1} \frac{N- a_p b_p}{p} y_p) p + t_{p2} p^2$

Step $\log_p N$
$x_p= P^{\log_p N}(y)+ t_{p\log_p N} p ^ {\log_p N}$ where $P^{\log_p N}(y)$ is a univariate polynomial on $y$ of degree $\log_p N$

Final Step
In other words $x_p = P^{\log_p N}(y) \mod p ^ {\log_p N}$ Substituting this into original equation we will get modular univariate polynomial equation of degree $\log_p N+1$. We need to factorize it and check $\log_p N+1$ values of resulted $x_p$.

I’ll leave the analysis of algorithm complexity to professionals. Have fun.