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 .

*Step 0*

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 .

*Step 1*

One can observe that , so we can write since . In other words . Substituting it into original equation we get . Summarizing,

.

* Step 2*

.

…

* Step *

where is a univariate polynomial on of degree

* Final Step *

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.

We get the system of modular poly equations at the end of recursion. I need to check whether final sysyem has nontrivial solution. Since it is growing power it may have low complexity solution.