pith. sign in

arxiv: 2508.00907 · v2 · submitted 2025-07-29 · 🧮 math.OC · cs.CR· physics.comp-ph· quant-ph

Prime Factorization Equation from a Tensor Network Perspective

Alejandro Mata Ali , Jorge Mart\'inez Mart\'in , Sergio Mu\~niz Subi\~nas , Miguel Franco Hernando , Javier Sedano , \'Angel Miguel Garc\'ia-Vico This is my paper

Pith reviewed 2026-05-19 03:13 UTC · model grok-4.3

classification 🧮 math.OC cs.CRphysics.comp-phquant-ph
keywords tensor networksinteger factorizationcombinatorial optimizationtensor train compressionmultiplication circuitdivisor search
0
0 comments X

The pith

A tensor network exactly encodes the search for nontrivial divisors by tensorizing a binary multiplication circuit and projecting its output onto the target integer.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out an explicit tensor-network equation that locates nontrivial divisors of any composite integer. It achieves this by converting a binary multiplication circuit into tensors and constraining the output register to equal the number to be factored. A sympathetic reader would see this as recasting factorization as a contraction problem that can be attacked with classical tensor methods rather than exhaustive search. The construction includes optimizations that shrink the auxiliary register while keeping at least one valid factor pair possible, and it supports both exact contraction and approximate tensor-train compression. Performance is checked on small instances to verify that the network can be evaluated.

Core claim

The paper presents an exact and explicit tensor-network equation for the search of nontrivial divisors of a composite integer. The network is built by tensorizing a binary multiplication circuit and projecting its output onto the target integer, with further reductions in auxiliary register size and tensor dimensions that still preserve at least one valid factorization orientation, all computable by contraction algorithms.

What carries the argument

The tensor network obtained by tensorizing a binary multiplication circuit, projecting its output register onto the target composite integer, and applying a reduced auxiliary register together with an optimized contraction scheme.

If this is right

  • Factorization becomes a tensor-contraction task rather than a direct search over possible divisors.
  • The reduced auxiliary register still guarantees that at least one correct factor pair remains representable.
  • Both exact contraction and approximate tensor-train methods can be used to evaluate the network.
  • The same construction template applies to other combinatorial optimization problems via the underlying MeLoCoToN framework.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar circuit-tensorization steps could be applied to other number-theoretic search tasks such as finding quadratic residues or solving discrete logarithms.
  • Systematic scaling tests on composites with increasing bit length would show whether contraction cost remains sub-exponential in practice.
  • The method may connect to existing tensor-network techniques used for satisfiability or graph problems by sharing the same contraction primitives.

Load-bearing premise

Contracting the optimized tensor network, even after auxiliary-register reduction and tensor-train compression, will locate at least one valid factorization orientation for the composite integers of interest.

What would settle it

Contract the network for the composite number 91 and check whether the contraction returns the divisor pair 7 and 13 or returns no divisors at all.

Figures

Figures reproduced from arXiv: 2508.00907 by Alejandro Mata Ali, \'Angel Miguel Garc\'ia-Vico, Javier Sedano, Jorge Mart\'inez Mart\'in, Miguel Franco Hernando, Sergio Mu\~niz Subi\~nas.

Figure 1
Figure 1. Figure 1: Logical circuit of the binary addition between two numbers. a), b) and c) [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Logical circuit of the binary multiplication between two numbers [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: a) Logical circuit that performs the multiplication in binary terms of two [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Tensorization of a six indexes operator with 3 inputs and 3 outputs that has [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Tensor network of the prime factorization for five bits number [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Exact contraction scheme from bottom-up. Last row is contracted, and the [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Exact contraction scheme from left-right. First column is contracted, and [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Execution time vs number n of bits of N. In blue points the time for each instance and in red squares the average total time. The purple star are the contraction time and the green triangles are the rest of time. 4 Performance evaluation and results In this section, the correctness of the presented equation and the performance of its calculation are evaluated. The exact case is implemented by means of bott… view at source ↗
Figure 9
Figure 9. Figure 9: Minimal bond dimension χmin vs number n of bits of N for different con￾traction schemes. It can be observed that the minimum bond dimension grows exponentially with the number of bits of the number to factorize. This implies that the algorithm continues to scale exponen￾tially with the size of the problem. However, the scaling is much smaller than in the exact case since it arrives at bond dimensions much … view at source ↗
Figure 10
Figure 10. Figure 10: Maximum possible compression vs number n of bits of N for different contraction schemes. being n(x, y) the number of bits with value y in binary form of x. The results of Figs. 11 show a relation cannot be directly deduced in the left-right scheme, but it seems that there may be a dependency in the bottom-up. However, given the sample, no relation can be concluded. 0.1 0.2 0.3 0.4 0.5 n0 40 60 80 100 (a) … view at source ↗
Figure 11
Figure 11. Figure 11: Minimal bond dimension vs n0 for different contraction schemes. Finally, it is checked if there is a possibility that, although the bond dimension used is lower than the minimum necessary, the result obtained allows us to obtain part of the information of the correct solution. The bit-flip error is defined as B = Xn−1 i=0 (1 − xi )pi + xi (1 − pi ) n . (13) As can be seen in Figs. 12 , there does not appe… view at source ↗
Figure 12
Figure 12. Figure 12: Bit-flip rate B vs the proportion χ χmin for different contraction schemes. equation has been computed with classical computational resources and its correctness and exponential scaling have been verified. In the approximated computation, the tensor train compression has been studied to improve its performance, but the results remain exponen￾tial. Nevertheless, the results, with high compression, indicate… view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to present an exact and explicit tensor-network equation for searching nontrivial divisors of a composite integer N, obtained by tensorizing a binary multiplication circuit and projecting its output register onto N. It describes optimizations including a reduced auxiliary register that preserves at least one valid factorization orientation, tensor-train compression for approximate contraction, and an associated algorithm, with tests performed using both exact and approximate contractions.

Significance. If the contraction remains tractable for relevant bit lengths, the work would supply a concrete tensor-network formulation of integer factorization within the MeLoCoToN framework, potentially linking combinatorial optimization techniques to number-theoretic search problems. The explicit circuit-to-tensor mapping is a clear constructive element.

major comments (2)
  1. Abstract: the statement that 'a series of tests ... evaluating its performance' is made, yet no quantitative metrics (runtime, success rate, error bounds, or scaling with bit length), error analysis, or comparisons against standard factoring methods appear. This leaves the efficiency claim of the algorithm unsupported.
  2. Section on auxiliary-register reduction and tensor-train compression: the assertion that the reduced register 'still preserves at least one valid factorization orientation' is stated without a proof, invariant, or explicit check that this orientation survives truncation; no bound on post-compression bond dimension or contraction complexity is supplied, so the method may still incur exponential cost in bit length.
minor comments (2)
  1. Notation: define the precise index ranges and contraction order for the multiplication tensors and the projection operator onto N so that the tensor-network equation can be reproduced unambiguously.
  2. Figure clarity: ensure that any diagrams of the tensor network or contraction scheme label all bond dimensions and the reduced auxiliary indices.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We address each major comment point by point below, indicating where revisions will be made to strengthen the presentation while remaining faithful to the work performed.

read point-by-point responses

  1. Referee: Abstract: the statement that 'a series of tests ... evaluating its performance' is made, yet no quantitative metrics (runtime, success rate, error bounds, or scaling with bit length), error analysis, or comparisons against standard factoring methods appear. This leaves the efficiency claim of the algorithm unsupported.

    Authors: We agree that the abstract would benefit from greater specificity. The manuscript reports numerical experiments on small composite integers, demonstrating successful recovery of factors via both exact contraction and tensor-train approximation. In the revision we will update the abstract to reference these concrete demonstrations and expand the main text with quantitative details including observed runtimes, success rates across tested bit lengths, and a basic error analysis for the approximate contractions. Direct benchmarking against classical algorithms such as trial division lies outside the present scope, which focuses on establishing the tensor-network formulation; we will note this limitation explicitly. revision: yes

  2. Referee: Section on auxiliary-register reduction and tensor-train compression: the assertion that the reduced register 'still preserves at least one valid factorization orientation' is stated without a proof, invariant, or explicit check that this orientation survives truncation; no bound on post-compression bond dimension or contraction complexity is supplied, so the method may still incur exponential cost in bit length.

    Authors: We acknowledge that a formal justification is currently missing. The register reduction is constructed to retain the minimal degrees of freedom required for the multiplication circuit to produce the target output N, thereby keeping at least one valid factorization path. We will insert a short lemma or invariant argument in the revised section establishing this preservation. For the tensor-train step we will add an analysis of bond-dimension growth together with the resulting contraction complexity, noting that exponential scaling in bit length cannot be ruled out in the worst case but that the approach yields practical gains on the moderate-size instances examined. We will also include explicit verification that valid orientations remain after truncation in the reported examples. revision: yes

Circularity Check

0 steps flagged

No significant circularity; formulation is a direct tensorization of multiplication circuit.

full rationale

The paper derives its tensor-network equation by explicitly tensorizing a binary multiplication circuit and projecting the output register onto the target integer N. This modeling step is presented as exact and first-principles, with subsequent optimizations (reduced auxiliary register preserving at least one factorization orientation, tensor-train compression) described as efficiency improvements rather than fitted inputs or self-referential definitions. The MeLoCoToN reference provides context for the general method but does not bear the load of the central claim, which remains independently verifiable against the circuit structure. No reduction of a prediction to its own inputs, no uniqueness theorem imported from self-citation, and no renaming of known results occur. The derivation chain is self-contained against the multiplication circuit benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The method inherits the MeLoCoToN combinatorial-optimization framework and assumes that a reduced auxiliary register still preserves at least one valid factorization path; no explicit free parameters or new entities are stated in the abstract.

axioms (1)
  • domain assumption A binary multiplication circuit can be faithfully represented as a tensor network whose contraction yields the product.
    Invoked when the authors tensorize the multiplication circuit and project its output onto the target integer.

pith-pipeline@v0.9.0 · 5683 in / 1084 out tokens · 37144 ms · 2026-05-19T03:13:11.753098+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages · 1 internal anchor

  1. [1]

    Montgomery , A survey of modern integer factorization algorithms , CWI quarterly 7, 337 (1994)

    L. Montgomery , A survey of modern integer factorization algorithms , CWI quarterly 7, 337 (1994)

    work page 1994

  2. [2]

    Sharp, R

    T . Sharp, R. Khare, E. Pederson and F . L. Traversa,Scaling up prime factorization with self- organizing gates: A memcomputing approach , doi:10.48550 /arXiv.2309.08198 (2023), 2309.08198

    work page arXiv 2023

  3. [3]

    M. A. Mobin and M. Kamrujjaman, Cryptanalysis of rsa cryptosystem: Prime factorization using genetic algorithm, doi:10.48550 /arXiv.2407.05944 (2024), 2407.05944

    work page arXiv 2024

  4. [4]

    R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital sig- natures and public-key cryptosystems , Commun. ACM 21(2), 120–126 (1978), doi:10.1145/359340.359342

    work page doi:10.1145/359340.359342 1978

  5. [5]

    Boudot, P

    F . Boudot, P . Gaudry , A. Guillevic, N. Heninger, E. Thomé and P . Zimmermann,Com- paring the difficulty of factorization and discrete logarithm: A 240-digit experiment , In D. Micciancio and T . Ristenpart, eds.,Advances in Cryptology – CRYPTO 2020, pp. 62–91. Springer International Publishing, Cham, ISBN 978-3-030-56880-1, doi:10.1007 /978- 3-030-5688...

    work page 2020

  6. [6]

    Shor, Algorithms for quantum computation: discrete logarithms and factoring, in: Pro- ceedings 35th Annual Symposium on Foundations of Computer Science, 1994, pp

    P . Shor, Algorithms for quantum computation: discrete logarithms and factoring , In Proceedings 35th Annual Symposium on Foundations of Computer Science , pp. 124–134, doi:10.1109/SFCS.1994.365700 (1994)

    work page doi:10.1109/sfcs.1994.365700 1994

  7. [7]

    Beauregard, Circuit for shor’s algorithm using 2n+3 qubits, Quantum Info

    S. Beauregard, Circuit for shor’s algorithm using 2n+3 qubits, Quantum Info. Comput. 3(2), 175–185 (2003), doi:10.26421/QIC3.2-8

    work page doi:10.26421/qic3.2-8 2003

  8. [8]

    Häner, M

    T . Häner, M. Roetteler and K. M. Svore, Factoring using 2n + 2 qubits with tof- foli based modular multiplication , Quantum Info. Comput. 17(7–8), 673–684 (2017), doi:10.26421/QIC17.7-8

    work page doi:10.26421/qic17.7-8 2017

  9. [9]

    Jun and H

    K. Jun and H. Lee,Hubo and qubo models for prime factorization, Scientific Reports13(1) (2023), doi:10.1038 /s41598-023-36813-x

    work page 2023

  10. [10]

    Sobhani, Y

    M. Sobhani, Y. Chai, T . Hartung and K. Jansen,Variational quantum eigensolver approach to prime factorization on ibm’s noisy intermediate scale quantum computer, Phys. Rev. A 111, 042413 (2025), doi:10.1103 /PhysRevA.111.042413

    work page 2025

  11. [11]

    Tensor Networks in a Nutshell

    J. Biamonte and V . Bergholm, Tensor networks in a nutshell , doi:10.48550/arXiv.1708.00006 (2017), 1708.00006. 17 SciPost Physics Submission

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1708.00006 2017

  12. [12]

    I. V . Oseledets,Tensor-train decomposition, SIAM Journal on Scientific Computing33(5), 2295 (2011), doi:10.1137 /090752286, https: //doi.org/10.1137/090752286

    work page doi:10.1137/090752286 2011

  13. [13]

    Tesoro, I

    M. Tesoro, I. Siloi, D. Jaschke, G. Magnifico and S. Montangero, Quantum inspired fac- torization up to 100-bit rsa number in polynomial time, doi:10.48550 /arXiv.2410.16355 (2024), 2410.16355

    work page arXiv 2024

  14. [14]

    A. M. Ali, Explicit solution equation for every combinatorial problem via tensor networks: Melocoton, doi:10.48550 /arXiv.2502.05981 (2025), 2502.05981

    work page arXiv 2025

  15. [15]

    Lopez-Piqueres and J

    J. Lopez-Piqueres and J. Chen, Cons-training tensor networks: Embedding and optimization over discrete linear constraints , SciPost Phys. 18, 192 (2025), doi:10.21468/SciPostPhys.18.6.192

    work page doi:10.21468/scipostphys.18.6.192 2025

  16. [16]

    R. S. Lehman, Factoring large integers , Mathematics of Computation 28(126), 637 (1974), doi:10.2307 /2005940

    work page 1974

  17. [17]

    J. D. Dixon, Asymptotically fast factorization of integers , Mathematics of Computation 36, 255 (1981)

    work page 1981

  18. [18]

    Pomerance, The quadratic sieve factoring algorithm , In T

    C. Pomerance, The quadratic sieve factoring algorithm , In T . Beth, N. Cot and I. Inge- marsson, eds., Advances in Cryptology, pp. 169–182. Springer Berlin Heidelberg, Berlin, Heidelberg, ISBN 978-3-540-39757-1, doi:10.1007 /3-540-39757-4_17 (1985)

    work page 1985

  19. [19]

    Lenstra, H

    A. Lenstra, H. Lenstra, M. Manasse and J. Pollard, The number field sieve , In Pro- ceedings of the 22nd Annual ACM Symposium on Theory of Computing , pp. 564–572, doi:10.1145/100216.100295 (1990)

    work page doi:10.1145/100216.100295 1990

  20. [20]

    P . W . Shor,Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer , SIAM Journal on Computing 26(5), 1484–1509 (1997), doi:10.1137/s0097539795293172

    work page doi:10.1137/s0097539795293172 1997

  21. [21]

    Kourtis, C

    S. Kourtis, C. Chamon, E. R. Mucciolo and A. E. Ruckenstein, Fast counting with tensor networks, SciPost Phys. 7, 060 (2019), doi:10.21468 /SciPostPhys.7.5.060

    work page 2019

  22. [22]

    A. M. Ali, Ftnilo: Explicit multivariate function inversion, optimization and counting, cryptography weakness and riemann hypothesis solution equation with tensor networks , doi:10.48550/arXiv.2505.05493 (2025), 2505.05493

    work page doi:10.48550/arxiv.2505.05493 2025

  23. [23]

    J. R. Pareja Monturiol, D. Pérez-García and A. Pozas-Kerstjens, TensorKrowch: Smooth integration of tensor networks in machine learning , Quantum 8, 1364 (2024), doi:10.22331/q-2024-06-11-1364, 2306.08595. 18

    work page doi:10.22331/q-2024-06-11-1364 2024