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 , where we know and want to find prime factors and .
Lets take small prime , than we can write .
One can observe that , since multiplication group modulo prime is cyclic for each there is unique satisfying the equation. In other words we need to test values to find correct one, if we can. From now on I assume satisfy and therefore divides .
One can observe that , so we can write since . In other words . Substituting it into original equation we get . Summarizing,
where is a univariate polynomial on of degree
In other words Substituting this into original equation we will get modular univariate polynomial equation of degree . We need to factorize it and check values of resulted .
I’ll leave the analysis of algorithm complexity to professionals. Have fun.