Predicting Prime Factor Sums of Odd Semiprimes via Modular Residues: A Conjecture on Prime Factor Sums

Predicting Prime Factor Sums of Odd Semiprimes via Modular Residues: A Conjecture on Prime Factor Sums Chandhru Srinivasan* Molecular Oncology Laboratory, Department of Biochemistry, School of Life Sciences, Bharathidasan University, Tiruchirappalli, Tamil Nadu, 620 024, India. Email: [email protected] ORCID: 0009-0004-5621-825X Abstract This work presents empirical evidence for a novel phenomenon concerning the sums of prime factors of odd semiprimes. For a semiprime 𝑁=𝑝⋅𝑞, where 𝑝,𝑞 are odd primes, this work investigates the modular residue properties of the sum 𝑠=𝑝+𝑞 modulo a dynamically chosen modulus 𝑚. We conjecture that 𝑠 (mod 𝑚) lies within a small subset 𝑅𝑚⊂ℤ𝑚 whose size grows sublinearly relative to 𝑚. By combining multiple such modular constraints via the Chinese Remainder Theorem (CRT), the candidate space for 𝑠 shrinks dramatically and help us to reconstruct the prime factors, leading to potential improvements in semiprime factorization algorithms. Keywords: Semiprimes, modular arithmetic, factorization, number theory. 1. Introduction: The factorization of composite integers, particularly semiprimes, is a classical problem in number theory with deep theoretical and practical significance (Crandall and Pomerance, 2001). Semiprimes — numbers that are the product of exactly two prime factors — play a central role in cryptography, computational number theory, and the study of arithmetic structures (Rivest et al., 1978). Most known factoring methods rely on probabilistic searches or smoothness methods (Brent, 1980; Lenstra, 1987; Pollard, 1975). In contrast, this study explores whether intrinsic modular structures in semiprimes encode deterministic information about their factors. Despite extensive research, the development of efficient deterministic methods for factorization remains a major challenge (Bressoud and Wagon, 2000). In this note, this work presents the conjecture on the behavior of the sum of semiprime factors, 𝑠=𝑝+𝑞, in modular arithmetic. Specifically, this work observed that for any odd semiprime 𝑁 and a chosen modulus 𝑚 or any combinations of moduli, the value 𝑠 mod 𝑚 is constrained to a surprisingly small subset of ℤ𝑚. Empirical experiments confirm this behavior across a wide range of semiprimes, and the reduction in candidate values for 𝑠 enables a significant narrowing of the search space for factorization. 2. Conjecture: Semiprime modular restriction Conjecture Let 𝑁=𝑝𝑞, where 𝑝 and 𝑞 are distinct odd primes, and define 𝑠=𝑝+𝑞. Then for any modulus 𝑚∈ℕ, there exists a set 𝑅𝑚⊂ℤ𝑚 such that: 1. 𝑠 mod 𝑚∈𝑅𝑚 2. ∣𝑅𝑚∣≪𝑚, with empirical evidence suggesting: ∣𝑅𝑚∣ 𝑚→0 as 𝑚→∞ 3. Multiple such congruences: 𝑠≡𝑟𝑖mod 𝑚𝑖,𝑟𝑖∈𝑅𝑚𝑖 can be combined via CRT to isolate 𝑠mod 𝑀, with 𝑀=lcm(𝑚1,…,𝑚𝑘). 4. Once 𝑀>𝑠, the value of 𝑠 is fully recovered and thus 𝑝 and 𝑞 are efficiently computed. 2.1 The key properties of this system are: i. Self-Contained Construction: The calculation of each residue set {𝑅𝑚} requires only the value of N. ii. Guaranteed Constraint: The true factor sum is guaranteed to satisfy the congruence 𝑆𝑁 (𝑚𝑜𝑑 𝑚)∈𝑅𝑚 for every or all chosen moduli. 3. Methodology: To evaluate the proposed modular constraint behaviour on semiprime factor sums, we implemented a custom Python script using only standard libraries. 3.1. Precomputation of Modular Signatures The core of this method is a one-time overhead to generate and store a database of all possible modular restrictions on the factor sum, 𝑆𝑁=𝑝+𝑞. This process is performed once for a selected set of moduli or any moduli {𝑚1,𝑚2,…,𝑚𝑘}. 3.1.1. Choice of Moduli: The system's effectiveness is enhanced by using a diverse set of moduli. This implementation includes primorials (e.g., 30,210,2310,30030), which are products of the first primes, as well as smaller semiprimes (e,g., 13,17,19,23) and a few composites (e.g., 100,300,360). This variety is lower the computation burden and the explosion of CRT combinations. 3.1.2. The Signature Database: For each modulus 𝑚, I generate a key-value map, which I term the modular signature. This map is stored as a JSON file or a similar dictionary structure. The key is a possible residue of a semiprime modulo 𝑚, i.e., 𝑘=𝑁(𝑚𝑜𝑑𝑚). The value is the restricted set of allowed residues for the factor sum, 𝑅𝑚={𝑟1,𝑟2,…} , where one of 𝑟𝑗≡(𝑝+𝑞)(𝑚𝑜𝑑𝑚). 3.2. Algorithm for Signature Generation The modular signature for each modulus is generated using the following algorithm: 1. Potential Factor Residues: Since is an odd semiprime, its factors and must be odd. Therefore, the set of all possible factor residues modulo 𝑚 is defined as {1,3,5,…,𝑘} , where 𝑘 is the largest, odd integer less than 𝑚. 2. Generate Semiprime Residues: All possible residues of 𝑁(𝑚𝑜𝑑 𝑚)are computed by taking the outer product of the factor residue set with itself: 𝑁𝑟𝑒𝑠≡𝑝⋅𝑞(𝑚𝑜𝑑 𝑚) for all pairs (𝑝,𝑞)∈𝑃𝑚×𝑃𝑚 . 3. Map to Factor Sum Residues: A dictionary is initialized. For each computed semiprime residue 𝑁𝑟𝑒𝑠 , compute the corresponding factor sum residue 𝑆𝑟𝑒𝑠≡𝑝+𝑞(𝑚𝑜𝑑 𝑚) and add it to a set associated with the key 𝑁𝑟𝑒𝑠. 4. Store the Signature: After iterating through all pairs, the resulting dictionary, which now represents the complete modular signature for 𝑚, is saved to a file. The python code and example modular signature files for the computations are available in the following Github repository: https://github.com/chandhruyuva006/Modular_constraint_based_integer_factorisation 3.3. Factorization via Signature Lookup and CRT Once the database is precomputed, factoring any new large semiprime N becomes an efficient lookup-based process: 3.3.1. Residue Calculation and Lookup: For each modulus in our precomputed set, I calculate the residue 𝑘𝑖=𝑁(𝑚𝑜𝑑 𝑚𝑖). I then perform a lookup in our database to fetch the corresponding restricted set of factor sum residues, 𝑅𝑚𝑖. 3.3.2. Construct System of Congruences: This lookup process yields a system of congruences for the true factor sum 𝑆𝑁 : {𝑆𝑁 (𝑚𝑜𝑑 𝑚𝑖)∈𝑅𝑚𝑖 𝑆𝑁 (𝑚𝑜𝑑 𝑚𝑖)∈𝑅𝑚𝑖 𝑆𝑁 (𝑚𝑜𝑑 𝑚𝑖)∈𝑅𝑚𝑖 3.3.3. Solve for 𝑺𝑵: The Chinese Remainder Theorem (CRT) is used to solve this system. By combining the constraints from each modulus, the set of possible candidates for is drastically reduced and the modulus (𝑀𝑒𝑓𝑓) might become larger based on the chosen {𝑚𝑖,𝑚𝑖,…𝑚𝑖 } and I have a larger but sparse set of residues 𝑅𝑒𝑓𝑓 𝑤ℎ𝑒𝑟𝑒 𝑆𝑁 ∈{𝑟𝑖,𝑟𝑖…….𝑟𝑖} . An efficient search through this small solution space reveals the true value of 𝑆𝑁. 3.3.4. Final Factor Recovery: upon searching through the current constrained space the 𝑆𝑁 the factors and are found by solving the quadratic equation 𝑥2−𝑆𝑁𝑥+𝑁=0, whose roots are the desired factors. 3.4. Illustrative Example: Factoring N = 72011 Here I demonstrate the entire process with the semiprime 𝑁=72011 . For this example, I will use our precomputed modular signatures for two small moduli: a primorial modulus 𝑚1 = 30 and a prime modulus 𝑚2=17.(The choice of the selection of the moduli is solely on the empirical evidence and I have observed that combining a primorial, small prime which is not the factor of the primorial and a composite moduli gave optimal search space reduction. But the stacked use of prime moduli can lead to a CRT combination explosion and may increase the memory usage and the moduli should be carefully stacked with CRT rather than combined at once. The example is chosen simply for demonstrating the CRT combination explosion vs search space reduction tradeoff). (For the reader's reference, the true factors are 107 and 673, and the true factor sum is 107+ 673=780 ) Step 1: Signature Lookup First, I calculate the residue of N for each selected modulus and perform a lookup in our precomputed signature database. 1. For 𝑚1=30 : I. Calculate 𝑁 (𝑚𝑜𝑑 30)=72011 (𝑚𝑜𝑑 30)=11 . II. Perform a lookup in our signature file. The precomputed signature reveals the restricted set of possible factor sum residues: 𝑅30:{0,12,18}. III. This gives us our first congruence: 𝑆𝑁=0 𝑚𝑜𝑑 (30) 𝑜𝑟 12 𝑚𝑜𝑑(30) 𝑜𝑟= 18 𝑚𝑜𝑑 (30). 2. For 𝑚1=17 : I. calculate 𝑁 (𝑚𝑜𝑑 17)=72011 (𝑚𝑜𝑑 17)=16. II. look up the key 17 in our file we have previously generated from the precomputation of modular signatures algorithm. Let's assume the precomputation yielded the set: 𝑅17:{0,2,5,6,8,9,11,12,15}. III. This gives us our second congruence: 𝑆𝑁∈ 𝑅17:{0,2,3,7,8,9,10,14,15}. (Note: we can verify our true factor sum 𝑆𝑁=780 satisfies these constraints: 0 (𝑚𝑜𝑑30) and 15 (𝑚𝑜𝑑15) or I can say that 𝑆𝑁∈ 𝑅30:{0,12,18} 𝑎𝑛𝑑 𝑅17:{0,2,3,7,8,9,10,14,15} Step 2: Solving the Congruence System: As 30 and 17 are coprime I can easily solve the CRT by creating all the possible combinations 𝑅𝑒𝑓𝑓 ={0,42…270,..480} (3∗8=24). But now the 𝑀𝑒𝑓𝑓 is also increased to 510. I can see that the 𝑅𝑒𝑓𝑓 is increased by a factor of 8 but the 𝑀𝑒𝑓𝑓 is increased by a factor of 17. 𝑆𝑁 is bounded by 2 ∗ √𝑁 𝑡𝑜 𝑁 . The start of 𝑆𝑁_𝑠𝑡𝑎𝑟𝑡 ≈ 536. From the 𝑅𝑒𝑓𝑓 I serve the possible candidates for the perfect square check and in less than 20 iterations I found the true 𝑆𝑁=780 which satisfies the 𝑆𝑁=270 𝑚𝑜𝑑(510). Step 3: Final Factor Recovery With the candidate value 𝑆𝑁=780, I can find the factors by solving the quadratic equation 𝑥2−780+72011=0. Solving the quadratic equation yields the unknown factors 𝑝 = 107,𝑞 =683. 3.5 Empirical testing: The conjecture was tested for N ranging from 1 − 1018. The code for this testing and example modular signature files for the computations is available in the following Github repository: https://github.com/chandhruyuva006/Modular_constraint_based_integer_factorisation 4. Conclusion This work presented a novel modular residue framework that significantly constrains the possible values of the factor sum 𝑠=𝑝+𝑞 for odd semiprimes 𝑁=𝑝𝑞. Our experiments show that, for suitable moduli 𝑚, the true value of 𝑠mod 𝑚lies within a small, predictable subset of ℤ𝑚, allowing for substantial reductions in the factor search space. While the primes 𝑝 and 𝑞 may be randomly distributed, the semiprime 𝑁 they form is not: it leaves a modular trace of its structure. Although reaching the exact factor sum remains computationally intensive for large 𝑁, our method reliably narrows the region where it must lie, revealing an underlying regularity in semiprime construction. We state this behavior as a conjecture and invite further mathematical investigation into its proof, properties, and potential cryptographic implications. Acknowledgements I sincerely thank Mr. Indhirakumar Murugesan, 12-B class members, PSGCAS class members, mathisfun.com members, Mr. Dario Alpern and open-source Python community for the standard library tools that enabled this implementation. Supplementary information and data availability: The code for this implementation and example modular signature files for the computations is available in the following Github repository: https://github.com/chandhruyuva006/Modular_constraint_based_integer_factorisation References: Brent, R.P., 1980. An improved Monte Carlo factorization algorithm. BIT 20, 176–184. https://doi.org/10.1007/BF01933190 Bressoud, D.M., Wagon, S., 2000. A course in computational number theory. Key College Publishing, in cooperation with Springer, New York. Crandall, R., Pomerance, C., 2001. Prime Numbers. Springer New York, New York, NY. https://doi.org/10.1007/978-1-4684-9316-0 Lenstra, H.W., 1987. Factoring Integers with Elliptic Curves. Ann. Math. 126, 649. https://doi.org/10.2307/1971363 Pollard, J.M., 1975. A monte carlo method for factorization. BIT 15, 331–334. https://doi.org/10.1007/BF01933667 Rivest, R.L., Shamir, A., Adleman, L., 1978. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 120–126. https://doi.org/10.1145/359340.359342