Prime Factorization Equation from a Tensor Network Perspective
This work addresses integer factorization, a problem of cryptographic importance, but the results are preliminary and incremental.
The paper presents an exact tensor-network equation for integer factorization based on a binary multiplication circuit, and tests it with tensor train compression. The method finds nontrivial divisors but no concrete performance numbers are reported.
This paper presents an exact and explicit tensor-network equation for the search of nontrivial divisors of a composite integer, together with an algorithm for its computation. The proposed method is based on the MeLoCoToN approach, which addresses combinatorial optimization problems through classical tensor networks. The presented tensor network tensorizes a binary multiplication circuit and projects its output onto the target integer to be factorized. Additionally, in order to make the algorithm more efficient, the number and dimension of the tensors and their contraction scheme are optimized, including a reduced auxiliary register that still preserves at least one valid factorization orientation. Finally, a series of tests on the algorithm are conducted, contracting the tensor network both exactly and approximately using tensor train compression, and evaluating its performance.