Applying System of Equations to Factor Semiprime Number

I. INTRODUCTION

Let , and be any integers such that , then

is a perfect square. Indeed

Let M be a semiprime number and let p, q be its prime factors, where q > p. Let d = q - p and let n and x be any integers, such that n divides M - x, then

is a positive integer. Thus, if is a non-negative perfect square, then

Equation (1.2) implies that

Hence, must contain a factor such that

The number must be of the form:

where j is an integer. Let k be a positive integer less than p, then substituting x with in equation (1.2) yields

Solving equation (1.3) for d we get the following two solutions

Sinceis a positive integer. The first equality of equation(1.4)implies that.

Substituting k with and n with in equation (1.3) yields and from this we get . Similarly, substituting k with and n with in equation (1.3) yields which gives us . This gives us the following system

System (1.6) has three equations with three variables n, k, d, however this system is dependent. We may overcome this problem by trying other functions. Let be any function, replace n with and k with u in equation (1.3). Equality (1.5) implies that (or ) and k - n = p (or n - k = p), which gives us a system of equations

from which we deduce or equivalently . We get the following equality:

II. BUILDING SYSTEMS OF EQUATIONS WITH

Based on equation (1.7) we can deduce a new system of three equations with three variables k, n and, d. We may find three functions and replace with to get the third equation, with to get the second equation, and finally with to get the first equation. The key here is to select the functions , and in such a way that our system has a unique solution, where . When moving to the left side of equality (1.7) and multiplying it with , the left side of this equality becomes:

If t is a polynomial function in R with integral coefficients, then can be viewed as a polynomial function from to R. In this case we also denote the function with . We thus get a system of polynomial equations:

III. BUILDING SYSTEMS OF EQUATIONS WITH

The problem with is that the variant of system (1.7) is infinite, any integer n,k such that satisfying this system. However, applying solution in equality (1.4) and requiring that n,k be positive integers implies that

Replacing n with and k with u in equation (1.3) we get the following system

from which we deduce or equivalently . Now we can replace with and with and with in equation (1.3) to get

Since relies on the second equality of (1.4) and since differs from , the first solution in (1.4) won't solve equality (3.3). Hence, by replacing with polynomial with positive coefficients we get two independent polynomials.

then equality (3.3) becomes

If we set , then equation (3.4) is equivalent to (1.3). However, if polynomial differs from n, then solution is lost. Hence, for any polynomial with positive integers that differs from n, polynomials and are independent.

We can repeatedly use the result , obtained from system (3.2), to get the following system of three polynomial equations with three variables:

If polynomials , and differ in pairs and having non-negative integers and if none of these polynomial is zero, then none of the polynomial in system (3.5) depends on the other.

IV. CONCLUSIONS

The RSA cryptosystem as well as all public key cryptography implementations rely on the complexity of semiprime factorization. Mathematical attacks based on known relations, such as Pythagorean primes or the use of a polynomial of third degree order have been recently proposed for potential methods for factoring semiprimes numbers. When it comes to factoring large semiprime numbers, well known existing algorithms may consume too much memory and running time. Other algorithms, such as the firefly algorithm , may address some of these issues .

In this article, we attempt to attack the problem of semiprime factorization by using relationships between M and two different numbers, that are less than M. Using only quadratic relationships, we have constructed a wide variety of systems of three polynomial equations with three variables. A solution of one of one system may lead to a complete factorization of the semiprime number M.

ACKNOWLEDGEMENTS

I would like to express my sincere gratitude to Professor Shai Haran, who provided invaluable feedback on the manuscript. His insightful comments and suggestions greatly improved the clarity and rigor of the research findings. I am grateful for his time and expertise, which helped me to refine my research questions and the methodology used to address them. Without his guidance, this paper would not have been possible.