P vs NP

I will publish the factorization of RSA260 on the 26th of December. I will also publish on the same date the factorization of RSA270 and RSA896. (the number of decimal digits of RSA270 and RSA896 is 270 but RSA896 is larger by one binary digit).

The algorithm for the traveling salesman problem (TSP) with distances a and b is a polynomial time algorithm. The time required by the algorithm grows with n, the size of the input, as n raised to the power of 2. The algorithm, not only, finds an optimal route, it can find all optimal routes, in a systematic way.

In the general case, every node is connected by an edge to every other node and the cost of every edge is either a or b. The Hamilton cycle problem, a more restricted case of the TSP, asks whether a tour of the graph exists. We can obtain an instance of the TSP with distances a and b from an instance of the Hamilton cycle problem in a straightforward way.

Transforming the factorization of RSA260 to the (undirected) Hamilton cycle problem yields an instance with 55,614,837 nodes and 84,899,139 edges. (an optimal tour will encode the two factors). Such a graph is a sparse graph. Solving the corresponding instance of the TSP with distances a and b, in contrast, is limited by the required amount of memory.

The algorithm can solve the Hamilton cycle problem directly. The corresponding weighted graph is provided as input. In this case, the amount of space and the amount of time needed by the algorithm can be drastically reduced. Thus, in practice, large instances of factoring and of other NP problems can be efficiently solved.

I will publish the factorization of RSA260 within a couple of weeks.

I stated in my previous post that the traveling salesman problem with distances a and b is easy. A consequence is factoring is also easy. Large numbers such as RSA numbers can be easily factored. I use the algorithm for the traveling salesman problem to factorize the RSA numbers that haven’t been factored yet, 31 numbers ranging from 260 to 617 digits. I’ll provide next more information and details.

Finding a polynomial time algorithm for any NP complete problem suffices to prove that P equals NP. Finding the shortest route to visit a number of cities once and return to the starting city is an optimization problem known as the traveling salesman problem (TSP). NP encompasses optimization problems and the TSP is one of the NP complete problems. I found a polynomial time algorithm for the special case of the TSP where distances are either a or b (a and b are positive integers and a < b). The TSP remains NP complete in this special case. The algorithm finds an optimal tour and its worst case running time is quadratic in the number of vertices. And there is a proof of the correctness and upper limit of the algorithm. The algorithm, in essence, lies at the core of the TSP, and thus, it throws light on the complexity of the TSP.

Prime factorization is an NP problem. RSA, a public key protocol widely used to secure data transmission over the Internet, works by using arithmetic modulo the product of two large prime numbers and relies on the assumption that factoring a number that is the product of two prime numbers with hundreds of digits is hard. An efficient algorithm for prime factorization can break RSA. Using the algorithm I found, I’ll soon factor all RSA numbers in the RSA Factoring Challenge that haven’t been factored so far, including RSA2048, and I’ll publish the solutions on this blog. I’ll start with RSA260.