The "Semiprime Tableau" is a visualization of the integer factorization problem viewed as a Constraint Satisfaction Problem (CSP) on a multiplication lattice. By representing the multiplication circuit geometrically, we attempt to expose symmetry-breaking constraints that are invisible to algebraic sieves.
We are given a composite integer \( N \) and seek prime factors \( P, Q \). In any radix base \( R \), we can represent these integers as polynomials:
The product \( N = P \times Q \) is formed by the convolution of these sequences, adjusted for carries. The digit at position \( k \) of the product \( N \) is determined by:
Where \( C_{k-1} \) is the carry accumulating from previous positions. This structure forms a "Tableau" or Lattice, specifically the Gelosia multiplication grid.
Standard RSA factoring algorithms (like GNFS) operate in algebraic number fields. However, our approach treats the multiplier circuit as a system of local constraints. Each cell \( c_{i,j} \) in our grid represents a "Radix Unit":
The geometry of the grid dictates that \( p_i \) is constant along rows and \( q_j \) is constant along columns. This creates a tightly coupled system. If we determine that \( c_{i,j} \) cannot have a remainder \( r \) modulo \( R \), we implicitly constrain the possible sets for \( p_i \) and \( q_j \).
The difficulty of this approach lies in the "Avalanche Effect" of the carry bits \( C_k \). However, Number Theory suggests the system is fragile.
Don Coppersmith (1997) proved that for an RSA modulus \( N = PQ \), if we know the high-order bits of \( P \) (specifically, \( \approx 50\% \) of the bits), we can recover the full factorization in polynomial time using Lattice Basis Reduction (LLL).
This suggests that we do not need to solve the entire tableau. We only need to find enough "cracks" in the symmetry—enough constraints on specific digits—to reach Coppersmith's threshold.
Attempts to convert factorization into SAT (Boolean Satisfiability) instances [Aloul 2003] generally fail on large integers. SAT solvers are "domain blind"—they treat carry bits as arbitrary logic gates. They do not utilize the rich structure of modulo arithmetic or the patterns of divisibility that exist in different Radices.
By allowing the user to switch Radix \( R \) (invoking the Chinese Remainder Theorem contextually), we effectively view the hidden solution through multiple geometric manifolds, seeking a projection where the symmetry breaks.