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.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

One Response to Semiprime factorization and modular arithmetics

  1. mkatkov says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s