# New Semi-Prime Factorization and Application in Large RSA Key Attacks
## 4 Proposed Method for Factoring Semi-Primes  
The inherent hardness of finding the prime factors of large semi-primes forms the fundamental premise for RSA robustness [53]. However, this holds good until there is an efficient method found to compute the unknown prime factors of RSA keys, which are essentially large semi-prime numbers [54]. While several methods for integer factorization exist in general [55, 56, 57], none of them focus on semi-prime factorization relating to RSA cryptosystems. Hence, in this paper we will take this challenge and focus on solving the semi-prime factorization problem with a proposed reduced problem approach. Through the rest of the paper, it will be shown that the problem can be reduced to finding only one suitable sum of three squares to factorize a semi-prime. We provide a mathematical proof for our proposed approach in this section. Proposed method: \"The sum of four squares factorization\" generates \(r4n\) solutions [48] (Equation (3)), of which only one solution is applicable to the Brahmagupta-Fibonacci identity, namely Equations (1) and (2). The remaining solutions do not lead to solutions for the semi-prime factorization. Some simple case examples are given below. **Case Example 1. ** Let us consider N = 169. \[169=13^{2}=\Big{(}2^{2}+3^{2}\Big{)}\Big{(}2^{2}+3^{2}\Big{)}=4^{2}+6^{2}+6^{2 }+9^{2}=4^{2}+4^{2}+4^{2}+11^{2}\]  
Applying the Brahmagupta-Fibonacci identity Equation (2), we obtain:  
\[4^{2}+6^{2}+6^{2}+9^{2}=(9-4)^{2}+(6+6)^{2}=5^{2}+12^{2}=(9+4)^{2}+(6-6)^{2}=1 3^{2}+0^{2}\]  
\[4^{2}+4^{2}+4^{2}+11^{2} \
eq(11-4)^{2}+(4+4)^{2}\ =\ 7^{2}+8^{2}\ =113\ \
eq 169\] \[4^{2}+\ 4^{2}+4^{2}+11^{2} \
eq (11+4)^{2}+(4-4)^{2}\ =\ 15+0^{2}\ =225\ \
eq 169\]  
**Case Example 2. ** Let us consider N = 377. \[377=(13)(29)=\Big{(}2^{2}+3^{2}\Big{)}\Big{(}2^{2}+5^{2}\Big{)}=4^{2}+6^{2}+10^ {2}+15^{2}\]  
Applying the Brahmagupta-Fibonacci identity provides the two sums of squares. \[377=4^{2}+6^{2}+10^{2}+15^{2}=(15-4)^{2}+(10+6)^{2}=\ 11^{2}+16^{2}=(15+4)^{2}+(1 0-6)^{2}=19^{2}+4^{2}\]  
\[377=4^{2}+19^{2}=11^{2}+16^{2}\]  
Once the two sums of two squares are known, the prime factors can be found using a modified Euler factorization [1]. \[\Delta e=16-4=12,\ \ \Delta o=19-11=8,\ \ \ g=\gcd(8,12)=4,\ \ \ p_{1}=\Big{(} \frac{8}{4}\Big{)}^{2}+\Big{(}\frac{12}{4}\Big{)}^{2}=13\]However, in this case, there are nine sums of four squares, as follows:  
\[(1,4,6,18),(1,6,12,14),(2,2,12,15),(2,6,9,16),(4,6,6,17)\]  
\[(\mathbf{4},\mathbf{6},\mathbf{10},\mathbf{15}),(5,8,12,12),(6,6,7,16),(6,8,9,14)\]  
Only one of these is applicable to the Brahmagupta-Fibonacci identity, providing the two sums of two squares. A faster method, using a modified binary greatest common divisor [14], quickly validates a sum of four squares given below:  
\[4^{2}+6^{2}+6^{2}+9^{2}=(9-4)^{2}+(6+6)^{2}=5^{2}+12^{2}=(9+4)^{2}+(6-6)^{2}=1 3^{2}+0^{2}\]0  
This requires the sums of four squares to be found until the correct sum of four squares is factored. This is not viable for the factorization of large semi-primes. In this paper, it will be shown that it is sufficient to find only one suitable sum of three squares to factorize a semi-prime, and a theorem proof and four lemmas follow. **Restating Theorem 1. **_If a Pythagorean quadruple has a square of a triple and \(N\) is semi-prime, then \(N\) can be factored. Some lemmas required are provided below._  
**Lemma 1. **_The square product of two primes (each sum of two squares) is four sums of three squares._  
**Proof. ** Consider the Lebesgue identity. The square of the sum of four squares can be given by the sum of three squares.