← Back
Fetching drawings from USPTO…
System and method for performing operation using linear-integer-programing for RSA factorization
Filed
2024-02-08
Issued
2026-05-05
Expires
2044-02-08
Fwd cites
0
Claims
12
Drawings
4
Drawings (3)
Agent Planner — multi-iter CAD reconstruction
No planner run yet. Click Run Planner → to start.
CAD Studio — AI 3D reconstruction
Synthesizing 3D model — Gemini vision → OpenSCAD → trimesh → PrusaSlicer (~30–60s)…
Abstract
A system for performing operations using linear integer programming for RSA factorization is provided, including an n/e extractor, a prime factorization calculator, a private key determiner, and a decryptor. The n/e extractor is configured to extract a modulus and a public key exponent from a public key. The prime factorization calculator is configured to: determine a semi-prime number of the modulus according to the modulus; use a tail digit and a head digit set of the semi-prime number of the modulus to perform decomposition and factorization with respect to the semi-prime number into two prime factors. The private key determiner is configured to determine a private key using the public key exponent and the two prime numbers. The decryptor is configured to decrypt an encrypted message using the private key so as to generate a decrypted message.
Claims (12)
- 11. A system for reducing computer processing time during private key decryption during digital communication, the system performing operations using linear integer programming for RSA factorization, comprising: an n/e extractor configured to extract a modulus and a public key exponent from a public key; a prime factorization calculator electrically coupled with the n/e extractor and configured to: determine a semi-prime number of the modulus according to the modulus; use a tail digit and a head digit set of the semi-prime number of the modulus to perform decomposition and factorization with respect to the semi-prime number into two prime factors via one of a first mode, a second mode, and a third mode, wherein the tail digit represents the last or least significant digit of the semi-prime number, and the head digit set represents the first two or most significant digits of the semi-prime number; and a private key determiner electrically coupled with the prime factorization calculator and configured to determine a private key using the public key exponent and the two prime numbers; and a decryptor electrically coupled with the private key determiner and configured to decrypt an encrypted message using the private key, so as to generate a decrypted message; wherein the prime factorization calculator is further configured to determine if the semi-prime number is in a form of 4k+1, k being a positive integer, wherein the decomposition and factorization is performed via the first mode as the semi-prime number is in the form of 4k+1, and the decomposition and factorization is performed via the third mode as the semi-prime number is not in the form of 4k+1; wherein the prime factorization calculator performs the decomposition by creating subproblems that are structured as linear integer programming problems, using the tail digit and the head digit set of the semi-prime number as decimal digit information, and performs the factorization by solving corresponding linear binary programs derived from the decomposition, such that, during execution of the private key decryption on a computer, the system solves the subproblems using linear integer programming techniques to reduce computer processing time and power consumption.
- 22. The system of claim 1, wherein the two prime factors are determined at the third mode, if the performing the decomposition and factorization by the prime factorization calculator begins from the third mode, as a form of 4m+1 and 4n+3 by the prime factorization calculator, where m and n are different positive integers, and m is not equal to n.
- 3
Description (21,104 words)
TECHNICAL FIELD
The present invention generally relates to the field of public-key encryption and digital signature, particularly to systems and methods for performing operations using linear integer programming for RSA factorization.
BACKGROUND
A semi-prime number is the product of exactly two different prime numbers. An RSA factorization method is to decompose a semi-prime number into its two prime factors. RSA factorization is an essential technique that is widely used in today's cryptography research such as the RSA public-key encryption and RSA digital signature. Many mathematicians and computer scientists have been developing new RSA factorization methods to secure today's digital communication systems.
Specifically, in RSA encryption, a public key is created from two large prime numbers, and the product of these two primes (a semiprime) is used as part of this key. The security of RSA encryption relies heavily on the computational difficulty of factoring large semiprime numbers. If it is easy to factorize the semiprime, the encryption could be easily broken, rendering the encrypted data insecure. A semiprime factorization calculator could theoretically be used to break RSA encryption by factorizing the semiprime number in the public key to find the original prime numbers. However, in practice, the prime numbers used in RSA encryption are so large (e.g., hundreds of digits) that it is computationally infeasible to factorize the semiprime number with current technology and known algorithms. Therefore, while a semiprime factorization calculator fits into the technical field of encryption/decryption in theory, its practical application for breaking modern encryption is currently limited.
The currently available RSA factorization methods using traditional computers can be casted in three categories. The first category, including the well-known “Trial Sieve method,” utilizes the exhaustive brute force techniques. The second category, including the “Pollard's Rho” and “Lenstra Elliptic Curve” methods develops special-purpose quadratic sieve methods. The third one is the general-purpose quadratic sieve category, including the General Number Field Sieve method (GNFS) and Shanks's method. There also exits an RSA factorization method using the quantum computer, which may become scalable in the future.
The above-mentioned RSA factoring methods have their features and limitations described as follows:
To factorize a semi-prime number θ, these methods may not utilize the information of decimal digits, but factorize θ directly.
These methods employ heuristic techniques, which may not converge to a final feasible solution. For example, the feasibility of GNFS method depends on how to specify the two polynomial functions involved, and the Pollard Rho method is a probabilistic algorithm with no guarantee to find a feasible solution.
To factorize a semi-prime number θ, a typical sieve method needs to know the prime numbers smaller than √{square root over (θ)} beforehand. For instance, the GNFS method spends more than half of its computing time (e.g., more than 50%) in detecting if a number is smooth or not. It is noted that a number is called B-smooth if all factors of the number are not larger than a number B.
Some of these methods can only factorize a semi-prime number θ with certain specific structure. For instance, SNFS can only factorizing θ with limited smoothness values.
Some of these methods, such as the Trial Division, Wheel Factorization, Pollard's Rho, and Elliptic Curve methods are special-purpose factoring algorithms, whose running time depends on the size of the smallest prime factor of θ.
Special-purpose factorization algorithms are usually applied to remove small factors before employing the General Quadratic Sieve method.
Therefore, there is a need to develop systems and methods for performing RSA factorization operations to address the challenges and shortcomings of the currently applied RSA factorization approaches.
SUMMARY OF INVENTION
It is an objective of the present invention to provide systems and methods for performing operations using linear integer programming for RSA factorization to address the aforementioned shortcomings and unmet needs in the state of the art.
To overcome the shortcomings of the current available RSA factorization methods, the present disclosure develops a novel RSA factorization approach, called Linear-Integer-Programming (LIP) method, for factorizing semi-prime numbers. The features of the LIP method are given in the following:
(i) To factorize a semi-prime primal θ with λ+2 decimal digits, LIP utilizes the decimal digit information of θ to formulate several subproblems in linear integer programming models with A equations and 10λ binary variables. Solving the resulting subproblems leads to the factorization of θ into two primes. This is totally different from the known methods, which do not use any of the decimal digit information of θ.
(ii) LIP is an exact method that can factorize any given semi-prime number into two exact primes without exception. It is different from the existing heuristic methods, which may not converge to a feasible solution.
(iii) To factorize a semi-prime number θ, the LIP method does not require the information of all primes smaller than √{square root over (θ)}.
(iv) LIP can factorize any given semi-prime number θ without asking θ to fit any required structure.
(v) LIP does not require the use of any specific software to factorize θ. Any commercially available linear integer programming solver can be utilized to factorize a given semi-prime number θ.
The strategy/key steps of developing the LIP method are described as follows:
(i) (Standard Expression) Given a semi-prime number θ in 1+2 decimal digits. Without loss of generality, in the decibel system, it can be assumed that A is an even number and
θ
=
∑
j
=
0
λ
a
j
×
1
0
j
,
where aj∈{0, 1, . . . , 9}, for j=0, 1, . . . , λ−1, and aλ{0, 1, . . . , 99}.
Example 1: For θ=123456, there is λ=4, a0=6, a1=5, a2=4, a3=3, a4=12, and θ=12×104+3×103+4×102+5×101+6×100. For θ=12345=012345, there is λ=4, a0=5, a1=4, a2=3, a3=2, a4=1, and θ=1×104+2×103+3×102+4×101+5×100.
In other words, for θ>0 in d>2 digits, if d is odd, then λ=d−1; otherwise, λ=d−2.
(ii) (Classification) It is to classify a semi-prime θ as a Type-1, Type-2, or Type-3 semi-prime number in the following way: (a) if θ=pi×pj, with pi and pj being 4k+1 primes, then θ is a type-1 semi-prime; (b) if θ=qi×qj with qi and qj being 4k+3, then θ is a Type-2 semi-prime; (c) if θ=pi×qj, with pi and qj being 4k+1 and 4k+3 primes, respectively, then θ is a type-3 semi-prime, where k∈N+.
(iii) (Representation) If θ is a Type-1 semi-prime, then there exist positive even integers m, m and odd integers n, n such that θ=m2+n2=m2+n2=4k+1. For example, Type-1 θ=221=13×17=102+112=142+52.
If θ is a Type-2 semi-prime, then there exist positive integers m and n (m even, n odd, and n>m) such that θ=n2−m2=4k+3. For example, Type-2 θ=77=7×11=92−22.
If θ is a Type-3 semi-prime, then there exist positive integers m and n (m even, n odd, and m>n) such that θ=m2−n2=4k+1. For example, Type-3 θ=143=13×11=122−12.
(iv) (Decomposition) Based on the digit-values of a0 and aλ, it is to decompose the main problem into several subproblems. Each subproblem is formulated as a linear integer programming problem with λ equations and 10λ binary variables.
(v) (Factorization) upon solving the corresponding linear binary programs to obtain m and n, then the exact factors of θ can be found accordingly.
In embodiments of the present disclosure, for a given semi-prime number
θ
=
∑
j
=
0
λ
a
j
×
1
0
j
(λθ is even), all decimal digits (from the tail digit a0 to the head two-digits aλ) are used to form subproblems for consideration. Hence, the approach can be called the “Linear-Integer-Programming” (LIP) method.
wherein
In accordance with a first aspect of the present invention, a system for reducing computer processing time during private key decryption during digital communication is provided. The system can perform operations using linear integer programming for RSA factorization, including an n/e extractor, a prime factorization calculator, a private key determiner, and a decryptor. The n/e extractor is configured to extract a modulus and a public key exponent from a public key. The prime factorization calculator is electrically coupled with the n/e extractor and is configured to: determine a semi-prime number of the modulus according to the modulus; use a tail digit and a head digit set of the semi-prime number of the modulus to perform decomposition and factorization with respect to the semi-prime number into two prime factors via one of a first mode, a second mode, and a third mode, in which the tail digit represents the last or least significant digit of the semi-prime number, and the head digit set represents the first two or most significant digits of the semi-prime number. The private key determiner is electrically coupled with the prime factorization calculator and is configured to determine a private key using the public key exponent and the two prime numbers. The decryptor is electrically coupled with the private key determiner and is configured to decrypt an encrypted message using the private key so as to generate a decrypted message.
In accordance with a second aspect of the present invention, a method for reducing computer processing time during private key decryption during digital communication is provided. The method is set for performing operations using linear integer programming for RSA factorization, including steps as follows: extracting a modulus and a public key exponent from a public key; determining a semi-prime number of the modulus according to the modulus; using a tail digit and a head digit set of the semi-prime number of the modulus to perform decomposition and factorization with respect to the semi-prime number into two prime factors via one of a first mode, a second mode, and a third mode, wherein the tail digit represents the last or least significant digit of the semi-prime number, and the head digit set represents the first two or most significant digits of the semi-prime number; determining a private key using the public key exponent and the two prime numbers;
and decrypting an encrypted message using the private key, so as to generate a decrypted message.
Specifically, the method can be expressed as the follows. (1): factor a given semi-prime
θ
=
∑
j
=
0
λ
a
j
10
j
into two primes, by solving λ+1 linear integer equations based on digital values a0, a1, a2, . . . , an; where λθ is even and aj are non-negative integers. (2) Let
X
=
∑
j
=
1
λ
x
j
1
0
j
,
and
Y
=
∑
j
=
1
λ
y
j
1
0
j
.
The solutions of factoring θ are expressed as:
(i) θ=X2+Y2, if θ=4k+1 and θ is the product of the 4k+1 primes.
(ii) θ=Y2−X2, if θ=4k+1 and θ is the product of the 4k+3 primes.
(iii) θ=X2−Y2, if θ=4k+3 and θ is the product of one 4k+1 prime and one 4k+3 prime.
(3A) Generate the equations solvable to obtain X and Y, which are expressed as:
x
0
2
+
y
0
2
=
10
w
0
+
a
0
2
∑
h
+
d
=
j
(
x
h
x
d
+
y
h
y
d
)
=
10
w
j
+
a
j
-
w
j
-
1
,
j
=
1
,
3
,
5
,
…
,
λ
-
1
,
2
∑
h
+
d
=
j
(
x
h
x
d
+
y
h
y
d
)
+
x
j
2
2
+
y
j
2
2
=
10
w
j
+
a
j
-
w
j
-
1
,
j
=
2
,
4
,
6
,
…
,
λ
-
2
,
x
λ
/
2
2
+
y
λ
/
2
2
=
10
w
λ
/
2
-
1
+
a
λ
,
where xhxd and yhyd can be linearized in the solution process.
(3B) Generate the equations solvable to obtain X and Y, which are expressed as:
y
2
-
x
0
2
=
10
w
0
+
a
0
,
2
∑
h
+
d
=
j
(
y
h
y
d
-
x
h
x
d
)
=
10
w
j
-
a
j
-
w
j
-
1
,
j
=
1
,
3
,
…
,
λ
-
1
,
2
∑
h
+
d
=
j
(
y
h
y
d
-
x
h
x
d
)
+
y
λ
/
2
2
-
x
λ
/
2
2
=
10
w
j
-
a
j
-
w
j
-
1
,
j
=
2
,
4
,
…
,
λ
-
2
,
y
λ
/
2
2
-
x
λ
/
2
2
=
10
w
λ
/
2
-
1
+
a
λ
,
where xhxd and yhyd can be linearized in the solution process.
(3C) Generate the equations solvable to obtain X and Y, which are expressed as:
x
0
2
-
y
0
2
=
10
w
0
+
a
0
,
2
∑
h
+
d
=
j
(
x
h
x
d
-
y
h
y
d
)
=
10
w
j
-
a
j
-
w
j
-
1
,
j
=
1
,
3
,
…
,
λ
-
1
,
2
∑
h
+
d
=
j
(
x
h
x
d
-
y
h
y
d
)
+
x
λ
/
2
2
-
y
λ
/
2
2
=
10
w
j
-
a
j
-
w
j
-
1
,
j
=
2
,
4
,
…
,
λ
-
2
,
where xhxd and yhyd can be linearized in the solution process.
(4) A parallel programming method can be devised to solve all linear integer equations above.
BRIEF DESCRIPTION OF DRAWINGS
Embodiments of the invention are described in more details hereinafter with reference to the drawings, in which:
FIG. 1 is a schematic block diagram of a system for performing operations using linear integer programming for RSA factorization according to an embodiment of the present invention;
FIG. 2 is a diagram of a Linear-Integer-Programming method for factorizing three types of θ according to an embodiment of the present invention; and
FIG. 3 is a block flowchart of a method for RSA factorization performed by a system according to an embodiment of the present invention.
DETAILED DESCRIPTION OF THE INVENTION
In the following description, systems and methods for performing operations using linear integer programming for RSA factorization and the likes are set forth as preferred examples. It will be apparent to those skilled in the art that modifications, including additions and/or substitutions may be made without departing from the scope and spirit of the invention. Specific details may be omitted so as not to obscure the invention; however, the disclosure is written to enable one skilled in the art to practice the teachings herein without undue experimentation.
RSA factorization is to decompose a semi-prime number into two prime factors, which is critical in today's public-key encryption. To factorize a semi-prime number θ, most of the currently available RSA factorization methods adopt a heuristic-based quadratic sieve techniques to decompose θ without utilizing much of the valuable decimal digit information inherent in θ. This invention develops a novel approach, called Linear-Integer-Programming (LIP) method, which employs the optimization-based integer programming techniques with the full decimal digit information in θ to decompose any given semi-prime number θ. To factorize a given θ in 1+2 decimals digits, the LIP first uses the tail (last, or least significant) digit and head (first two, or most significant) digits of θ to decompose the original problem into subproblems, then reformulate each subproblem as a linear integer program in λ equations and 10λ binary variables. By solving the resulting linear integer programs using any commercial software, θ can then be effectively factorized into two prime numbers.
FIG. 1 shows a schematic diagram of a system 100 for performing operations using linear integer programming for RSA factorization with respect to a sender terminal T1 and a receiver terminal T2 according to an embodiment of the present disclosure. The system 100 is provided for reducing computer processing time and/or computer power consumption during private key decryption during digital communication. The system 100 can act as a decryptor or decryption system, leading to a reduction in computer power consumption during the decryption process. This is achieved by enabling the completion of the decryption process with less computing power by using the system 100.
The sender terminal T1 can send an encrypted message EM to the receiver terminal T2 and receive a public key PK1 from the receiver terminal T2, associated with a private key PK2. In such a case, the public key PK1 may be published and thus obtainable directly or indirectly from the receiver terminal T2 by any participant; however, only the receiver terminal T2 has access to the private key PK2. The system 100 is configured to determine the private key PK2 from the public key PK1 to decrypt the encrypted message EM encrypted using the public key PK1. It can then further use the private key PK2 to decrypt the encrypted message EM, producing a decrypted message DM. Under the condition that the public key PK1 is obtainable by the system 100, the system 100 is able to determine or crack the private key PK2. To achieve it, in one embodiment, the system 100 include an n/e extractor 110, a prime factorization calculator 120, a private key determiner 130, a decryptor 140, and a result presenter 150.
The n/e extractor 110 is configured to extract one or more components of the public key PK1. In this regard, under the construction of Rivest-Shamir-Adleman (RSA) encryption, the public key PK1 contains a modulus n and a public key exponent e that are encoded in an encoded data structure. Correspondingly, in one embodiment, the n/e extractor 110 can extract the modulus n and the public key exponent e from the public key PK1 by a parser, so as to parse the encoded data structure representing the public key PK1.
The prime factorization calculator 120 is electrically coupled with the n/e extractor 110 is configured to receive the components of the public key PK1 from the n/e extractor 110, such as the modulus n, and take the components of the public key PK1 for factoring the modulus n into two prime factors in order to determining the private key PK2. Briefly, to factorize a given θ (e.g., a semi-prime number contained in a modulus n) in λ+2 decimals digits, during determining the private key PK2, the prime factorization calculator 120 can use the tail (last, or least significant) digit and head (first two, or most significant) digits of θ to decompose the original problem into subproblems, then reformulate each subproblem as a linear integer program in λ equations and 10λ binary variables. By solving the resulting linear integer programs, θ can then be effectively factorized into two prime numbers, so as to determine the private key PK2.
The private key determiner 130 is electrically coupled with the prime factorization calculator 120 and is configured to determine the private key PK2 using the public key exponent e and the two prime numbers obtained from the prime factorization calculator 120 factoring the modulus n. In the RSA cryptosystem, the private key PK2 shares the same modulus n as the public key PK1 but has a private key exponent d distinct from the public key exponent e. The private key determiner 130 derives the private key exponent d of the private key PK2 by utilizing the two prime numbers obtained from the prime factorization calculator 120. It uses these prime numbers to calculate the private key exponent d through specialized programs within the RSA cryptosystem, ensuring a distinct private key exponent from the public key exponent e. For example, once the modulus n of the public key and its two prime factors p and q are obtained, it can derive the private key d by calculating Euler's totient function, selecting the public key exponent e, and then computing the private key exponent d.
The decryptor 140 is electrically coupled with the private key determiner 130 and is configured to decrypt the encrypted message EM using the private key PK2 determined by the private key determiner 130. The decryptor 140 can analyze an encoded data structure representing the encrypted message EM, so as to parse the encoded data structure and accordingly extract a ciphertext c to be decrypted using the private key PK2 For example, as the encrypted message EM is represented as a base64-encoded string, the decryptor 140, through its analysis, can decode this string to obtain the ciphertext c, which is then subjected to decryption using the private key PK2. With the ciphertext c, the modulus n, and the private key exponent d determined by the private key determiner 130, the decryptor can successfully decrypt the ciphertext c.
The result presenter 150 is electrically coupled with the decryptor 140 and is configured to collect information from the decryptor 140 regarding the decrypted result, operating after the decryptor 140 successfully decrypts the encrypted message EM using the private key PK2 determined by the private key determiner 130. The result presenter 150 is electrically coupled with the receiver terminal T2, once the decryption process is completed and thus the decrypted message DM is generated/obtained, the result presenter 150 can extract relevant details from the decrypted message DM, presenting information about the original encrypted message EM, such as its content, metadata, or any associated data. The result presenter 150 can enhance the overall functionality by providing an interface to access and display decrypted message information after the decryption process is carried out by the decryptor 140.
In one embodiment, the prime factorization calculator 120 can program operations, including standard expression, classification, representation, decomposition, and factorization, so as to factor the modulus n into two prime factors, which are described in more detail below.
Remarks, propositions, and examples are provided to prove the prime factorization calculator 120 can achieve the factoring function. All prime numbers are positive odd numbers. There are two kinds of positive odd numbers, namely, the 4k+1 (k=1, 2, . . . ) integers and 4k+3 (k=0, 1, 2, . . . ) integers. When prime numbers are concerned, there are 4k+1 primes and 4k+3 primes. For instance, 5, 13, 17, 29 and 37 are 4k+1 primes, and 3, 7, 11, 19 and 23 are 4k+3 primes.
Remark 1: Denote pi as the ith 4k+1 prime, and denote q, as the jth 4k+3 prime. For instance, p1=5, p2=13, p3=17, q1=3, q2=7, q3=11.
Remark 2: An integer θ>0 is called a semi-prime number, if θ is the product of two different primes. There are three types of semi-prime numbers:
(i) θ is a Type-1 semi-prime, if θ is the product of two 4k+1 primes. For instance, θ=221=13×17 is a Type-1 semi-prime. In this case, θ is a 4k+1 integer.
(ii) θ is a Type-2 semi-prime, if θ is the product of two 4k+3 primes. For 4k+1 instance, θ=7×11=77 is a Type-2 semi-prime. In this case, θ is also a 4k+1 integer.
(iii) θ is a Type-3 semi-prime, if θ is the product of one 4k+1 prime and one 4k+3 prime. In this case, θ is a 4k+3 integer. For instance, θ=13×11=143 is a Type-3 semi-prime.
Proposition 1
For a semi-prime number θ, the followings statements are true:
(i) If θ is in the form of 4k+1, then either θ is a Type-1 semi-prime such that θ=pi×pj with pi, pj being 4k+1 primes, or θ is a Type-2 semi-prime such that θ=qi×qj with qi, qj being 4k+3 primes.
(ii) If θ is in the form of 4k+3, then θ is a Type-3 semi-prime such that θ=pi×qj with pi being a 4k+1 prime and q; being a 4k+3 prime.
Proposition 2
Let θ be a Type-1 semi-prime, then the following statements are true:
(i) There exist positive integers m, n, m, n with m>m being even and n<n being odd such that θ=m2+n2=m2+n2.
(ii) Take 2a=gcd(m−m, n−n), 2b=gcd(m+m, n+n), 2c=gcd(m−m, n+n), and 2d=gcd(m+m, n−n).
Set pi=a2+b2, pj=c2+d2, then pi and pj are 4k+1 primes and pi×pj=0.
Example 2: Consider θ=221=13×17. there is, m=14, m=10, n=5, n=11,
a
=
1
2
gcd
(
1
4
-
1
0
,
1
1
-
5
)
=
1
,
b
=
1
2
gcd
(
1
4
+
1
0
,
5
+
1
1
)
=
4
,
c
=
1
2
gcd
(
1
4
-
1
0
,
5
+
1
1
)
=
2
,
d
=
1
2
gcd
(
1
4
+
1
0
,
1
1
-
5
)
=
3
,
p
i
=
1
2
+
4
2
=
1
7
,
p
j
=
2
2
+
3
2
=
1
3
Proposition 3
Let θ be a Type-2 semi-prime, then the following statements are true:
(i) There exist positive integers m<n with even m and odd n such that
θ
=
n
2
-
m
2
=
(
n
+
m
)
(
n
-
m
)
=
q
i
×
q
j
.
For instance, given θ=77=7×11, there is m=2<n=9, and qi=9+2=11, qj=9−2=7.
Proposition 4
Let θ be a Type-3 semi-prime, then the following statements are true:
(i) There exist positive integers m>n with even m and odd n such that
θ
=
m
2
-
n
2
=
(
m
+
n
)
(
m
-
n
)
=
p
i
×
q
j
.
For instance, given θ=143=13×11, there is m=12, n=1, and pi=12+1=13, q; =12−1=11.
Let θ>0 be a semi-prime with λ>0, a positive even number, such that
θ
=
∑
i
=
0
λ
a
i
×
1
0
i
,
a
i
∈
{
0
,
1
,
…
,
9
}
for
i
=
0
,
…
,
λ
-
1
and
a
λ
∈
{
1
,
…
,
99
}
.
Proposition 5-1
If θ is Type-1 semi-prime, then 0 can be expressed as:
θ
=
m
2
+
n
2
=
(
∑
j
=
0
λ
/
2
x
j
×
1
0
j
)
2
+
(
∑
j
=
0
λ
/
2
y
j
×
1
0
j
)
2
=
(
x
0
2
+
y
0
2
)
×
1
0
0
+
2
(
x
0
x
1
+
y
0
y
1
)
×
1
0
1
+
[
x
1
2
+
y
1
2
+
2
(
x
0
x
2
+
y
0
y
2
)
]
×
1
0
2
+
2
(
x
0
x
3
+
y
0
y
3
+
x
1
x
2
+
y
1
y
2
)
×
1
0
3
+
[
x
2
2
+
y
2
2
+
2
(
x
0
x
4
+
y
0
y
4
+
x
1
x
3
+
y
1
y
3
)
]
×
1
0
4
+
2
(
x
0
x
5
+
y
0
y
5
+
x
1
x
4
+
y
1
y
4
+
x
2
x
3
+
y
2
y
3
)
×
1
0
5
+
⋯
+
[
x
{
λ
-
4
}
2
2
+
y
{
λ
-
4
}
2
2
+
2
(
x
λ
2
-
4
x
λ
2
+
y
λ
2
-
4
y
λ
2
+
x
λ
2
-
3
x
λ
2
-
1
+
y
λ
2
-
3
y
λ
2
-
1
)
]
×
1
0
λ
-
4
+
2
(
x
λ
2
-
3
x
λ
2
+
y
λ
2
-
3
y
λ
2
+
x
λ
2
-
2
x
λ
2
-
1
+
y
λ
2
-
2
y
λ
2
-
1
)
×
10
λ
-
3
+
[
x
{
λ
-
2
}
2
2
+
y
{
λ
-
2
}
2
2
+
2
(
x
λ
2
-
2
x
λ
2
+
y
λ
2
-
2
y
λ
2
)
]
×
1
0
λ
-
2
+
2
(
x
λ
2
-
1
x
λ
2
+
y
λ
2
-
1
y
λ
2
)
×
1
0
λ
-
1
+
(
x
λ
2
2
+
y
λ
2
2
)
×
1
0
λ
where
(i) x0 is even, y0 is odd,
(ii) x0, x1, . . . , xλ/2, y0, y1, . . . , yλ/2∈{0, 1, . . . , 9},
x
0
2
+
y
0
2
=
a
0
and
x
λ
/
2
2
+
y
λ
/
2
2
≤
a
λ
.
(
iii
)
Let θ>0 be a semi-prime with λ>0, a positive even number, such that
θ
=
∑
i
=
0
λ
a
i
×
1
0
i
,
a
i
∈
{
0
,
1
,
…
,
9
}
for
i
=
0
,
…
,
λ
-
1
and
a
λ
∈
{
1
,
…
,
99
}
.
Proposition 5-2
If θ is Type-2 semi-prime, then 0 can be expressed as
θ
=
-
m
2
+
n
2
=
-
(
∑
j
=
0
λ
/
2
x
j
×
1
0
j
)
2
+
(
∑
j
=
0
λ
/
2
y
j
×
1
0
j
)
2
=
(
-
x
0
2
+
y
0
2
)
×
1
0
0
+
2
(
-
x
0
x
1
+
y
0
y
1
)
×
1
0
1
+
[
-
x
1
2
+
y
1
2
+
2
(
-
x
0
x
2
+
y
0
y
2
)
]
×
1
0
2
+
2
(
-
x
0
x
3
+
y
0
y
3
-
x
1
x
2
+
y
1
y
2
)
×
1
0
3
+
[
-
x
2
2
+
y
2
2
+
2
(
-
x
0
x
4
+
y
0
y
4
-
x
1
x
3
+
y
1
y
3
)
]
×
1
0
4
+
2
(
-
x
0
x
5
+
y
0
y
5
-
x
1
x
4
+
y
1
y
4
-
x
2
x
3
+
y
2
y
3
)
×
1
0
5
+
⋯
+
[
-
x
{
λ
-
4
}
2
2
+
y
{
λ
-
4
}
2
2
+
2
(
-
x
λ
2
-
4
x
λ
2
+
y
λ
2
-
4
y
λ
2
-
x
λ
2
-
3
x
λ
2
-
1
+
y
λ
2
-
3
y
λ
2
-
1
)
]
×
10
λ
-
4
+
2
(
-
x
λ
2
-
3
x
λ
2
+
y
λ
2
-
3
y
λ
2
-
x
λ
2
-
2
x
λ
2
-
1
+
y
λ
2
-
2
y
λ
2
-
1
)
×
10
λ
-
3
+
[
-
x
{
λ
-
2
}
2
2
+
y
{
λ
-
2
}
2
2
+
2
(
-
x
λ
2
-
2
x
λ
2
+
y
λ
2
-
2
y
λ
2
)
]
×
1
0
λ
-
2
+
2
(
-
x
λ
2
-
1
x
λ
2
+
y
λ
2
-
1
y
λ
2
)
×
1
0
λ
-
1
+
(
-
x
λ
2
2
+
y
λ
2
2
)
×
1
0
λ
where
(i) x0 is even, y0 is odd,
x
0
,
x
1
,
⋯
,
x
λ
2
,
y
0
,
y
1
,
⋯
,
y
λ
2
∈
{
0
,
1
,
…
,
9
}
,
(
ii
)
-
x
0
2
+
y
0
2
=
a
0
and
-
x
λ
2
2
+
y
λ
2
2
≤
a
λ
.
(
iii
)
Let θ>0 a semi-prime with λ>0 being a positive even number such that
θ
=
∑
i
=
0
λ
a
i
×
1
0
i
,
a
i
∈
{
0
,
1
,
…
,
9
}
for
i
=
0
,
…
,
λ
-
1
and
a
λ
∈
{
1
,
…
,
99
}
.
Proposition 5-3
If θ is Type-3 semi-prime, then 0 can be expressed as
θ
=
m
2
-
n
2
=
(
∑
j
=
0
λ
/
2
x
j
×
1
0
j
)
2
-
(
∑
j
=
0
λ
/
2
y
j
×
1
0
j
)
2
=
(
x
0
2
-
y
0
2
)
×
1
0
0
+
2
(
x
0
x
1
-
y
0
y
1
)
×
1
0
1
+
[
x
1
2
-
y
1
2
+
2
(
x
0
x
2
-
y
0
y
2
)
]
×
1
0
2
+
2
(
x
0
x
3
-
y
0
y
3
+
x
1
x
2
-
y
1
y
2
)
×
1
0
3
+
[
x
2
2
-
y
2
2
+
2
(
x
0
x
4
-
y
0
y
4
+
x
1
x
3
-
y
1
y
3
)
]
×
1
0
4
+
2
(
x
0
x
5
-
y
0
y
5
+
x
1
x
4
-
y
1
y
4
+
x
2
x
3
-
y
2
y
3
)
×
1
0
5
+
⋯
+
[
x
{
λ
-
4
}
2
2
+
y
{
λ
-
4
}
2
2
+
2
(
x
λ
2
-
4
x
λ
2
-
y
λ
2
-
4
y
λ
2
+
x
λ
2
-
3
x
λ
2
-
1
-
y
λ
2
-
3
y
λ
2
-
1
)
]
×
1
0
λ
-
4
+
2
(
x
λ
2
-
3
x
λ
2
-
y
λ
2
-
3
y
λ
2
+
x
λ
2
-
2
x
λ
2
-
1
-
y
λ
2
-
2
y
λ
2
-
1
)
×
10
λ
-
3
+
[
x
{
λ
-
2
}
2
2
-
y
{
λ
-
2
}
2
2
+
2
(
x
λ
2
-
2
x
λ
2
-
y
λ
2
-
2
y
λ
2
)
]
×
1
0
λ
-
2
+
2
(
x
λ
2
-
1
x
λ
2
-
y
λ
2
-
1
y
λ
2
)
×
1
0
λ
-
1
+
(
x
λ
2
2
-
y
λ
2
2
)
×
1
0
λ
where
(i) x0 is even, y0 is odd,
x
0
,
x
1
,
⋯
,
x
λ
2
,
y
0
,
y
1
,
⋯
,
y
λ
2
∈
{
0
,
1
,
…
,
9
}
,
(
ii
)
x
0
2
-
y
0
2
=
a
0
and
x
λ
2
2
-
y
λ
2
2
≤
a
λ
.
(
iii
)
Example 3: A semi-prime θ=12,648,677,849 (d=11, λ=d−1=10) can be written as
θ
=
∑
i
=
0
1
0
a
i
×
1
0
i
=
1
×
1
0
10
+
2
×
1
0
9
+
6
×
10
8
+
4
×
1
0
7
+
8
×
1
0
6
+
,
6
×
1
0
5
+
7
×
1
0
4
+
7
×
1
0
3
+
8
×
1
0
2
+
4
×
10
1
+
9
×
10
0
with
(
a
10
,
a
9
,
a
8
,
⋯
,
a
0
)
=
(
1
,
2
,
6
,
4
,
8
,
6
,
7
,
7
,
8
,
4
,
9
)
.
Since θ=4k+1 type, it can be expressed as
θ
=
m
2
+
n
2
=
(
∑
j
=
0
5
x
j
×
1
0
j
)
2
+
(
∑
j
=
0
5
y
j
×
1
0
j
)
2
(
m
is
even
,
n
is
odd
)
=
(
x
0
2
+
y
0
2
)
×
1
0
0
+
2
(
x
0
x
1
+
y
0
y
1
)
×
1
0
1
+
[
x
1
2
+
y
1
2
+
2
(
x
0
x
2
+
y
0
y
2
)
]
×
1
0
2
+
2
(
x
0
x
3
+
y
0
y
3
+
x
1
x
2
+
y
1
y
2
)
×
1
0
3
+
[
x
2
2
+
y
2
2
+
2
(
x
0
x
4
+
y
0
y
4
+
x
1
x
3
+
y
1
y
3
)
]
×
1
0
4
+
2
(
x
0
x
5
+
y
0
y
5
+
x
1
x
4
+
y
1
y
4
+
x
2
x
3
+
y
2
y
3
)
×
1
0
5
+
[
x
3
2
+
y
3
2
+
2
(
x
1
x
5
+
y
1
y
5
+
x
2
x
4
+
y
2
y
4
)
]
×
1
0
6
+
2
(
x
2
x
5
+
y
2
y
5
+
x
3
x
4
+
y
3
y
4
)
×
1
0
7
+
[
x
4
2
+
y
4
2
+
2
(
x
3
x
5
+
y
3
y
5
)
]
×
1
0
8
+
2
(
x
4
x
5
+
y
4
y
5
)
×
1
0
9
+
(
x
5
2
+
y
5
2
)
×
1
0
1
0
Remark 3-1
Let θ be a Type-1 semi-prime. Denote Aj as the polynomial function associate with the term of 10j in the expression of θ for j=0, . . . , λ. Then, there are:
(i) If j=0, then A0=x02+y02.
(ii) If 0<j<θ is odd, then Aj=2Σ(h,l)∈Sj(xhxl+yhyl),
where Sj={(h,l) integers: h+l=j, 0≤h<l≤λ/2}.
(iii) If 0<j<λ is even, then Aj=xj/22+yj/22+2Σ(h,l)∈Sj(xhxl+yhyl).
(iv) If j=λ, then Aλ=xλ/22+yλ/22.
Proposition 6-1
For θ and Aj in Remark 3-1, it is true that
θ
=
A
0
×
1
0
0
+
A
1
×
1
0
1
+
…
+
A
λ
×
1
0
λ
=
∑
j
=
0
λ
A
j
×
1
0
j
.
Remark 3-2
Let θ be a Type-2 semi-prime. Denote Bj as the polynomial function associate with the term of 10j in the expression of θ for j=0, . . . , λ. Then, it is obtained as follows:
(i) If j=0, then B0=−x02+y02.
(ii) If 0<j<λ is odd, then Bj=2Σ(h,l)∈Sj(−xhxl+yhyl),
where Sj={(h,l) integers: h+l=j, 0≤h<l≤λ/2}.
(iii) If 0<j<λ is even, then Bj=xj/22+yj/22+2Σ(h,l)∈Sj(−xhxl+yhyl).
(iv) If j=1, then Bλ=−xλ/22+yλ2.
Proposition 6-2
For θ and Bj in Remark 3-2, it is true that
θ
=
B
0
×
1
0
0
+
B
1
×
1
0
1
+
…
+
B
λ
×
1
0
λ
=
∑
j
=
0
λ
B
j
×
1
0
j
.
Remark 3-3
Let θ be a Type-3 semi-prime. Denote Cj as the polynomial function associate with the term of 10j in the expression of θ for j=0, . . . , λ. Then there are:
(i) If j=0, then C0=x02−y02.
(ii) If 0<j<λ is odd, then Cj=2Σ(h,l)∈Sj(xhxl−yhyl),
where Sj={(h,l) integers: h+l=j, 0<h<l≤λ/2}.
(iii) If 0<j<λ is even, then Cj=xj/22+yj/22+2Σ(h,l)∈Sj(xhxl−yhyl).
(iv) If j=2, then Cλ=xλ/22−yλ/22.
Proposition 6-3
For θ and Cj in Remark 3-3, it is true that
θ
=
C
0
×
1
0
0
+
C
1
×
1
0
1
+
…
+
C
λ
×
1
0
λ
=
∑
j
=
0
λ
C
j
×
1
0
j
.
Remark 4-1
Notice that aj represents the digital value and Aj represents a polynomial function for j=0, . . . , λ, they are closely related in the following way:
Proposition 7-1
For Aj specified in Remark 3-1, there exist w0, . . . , wλ∈{0, 1, . . . , 16} such that the following equations are true:
A
0
=
x
0
2
+
y
0
2
=
10
w
0
+
a
0
(
i
)
A
j
=
10
w
j
+
a
j
-
w
j
-
1
,
j
=
1
,
…
,
λ
-
1
(
ii
)
where Aj=2Σ(h,l)∈Sj(xhxl+yhyl), when j is odd;
Aj=xj/22+yj/22+2Σ(h,l)∈Sj(xhxl+yhyl), when j is even;
and Sj={(h,l) integers: h+l=j, 0≤h<l≤λ/2}.
A
λ
=
x
λ
/
2
2
+
y
λ
/
2
2
+
=
10
w
λ
+
a
λ
-
w
λ
-
1
(
iii
)
Example 4: For a
θ
=
∑
j
=
0
10
a
j
×
1
0
λ
=
(
x
5
×
1
0
5
+
x
4
×
1
0
4
+
…
+
x
0
)
2
+
(
y
5
×
1
0
5
+
y
4
×
1
0
4
+
…
+
y
0
)
2
=
∑
j
=
1
10
A
j
×
1
0
λ
.
between Aj and aj can be expressed by equations below:
A
0
=
x
0
2
+
y
0
2
=
10
w
0
+
a
0
,
A
1
=
2
(
x
0
x
1
+
y
0
y
1
)
=
10
w
1
+
a
1
-
w
0
,
A
2
=
2
(
x
0
x
2
+
y
0
y
2
)
+
x
1
2
+
y
1
2
=
10
w
2
+
a
2
-
w
1
,
A
3
=
2
(
x
0
x
3
+
y
0
y
3
+
x
1
x
2
+
y
1
y
2
)
=
10
w
3
+
a
3
-
w
2
,
A
4
=
2
(
x
0
x
4
+
y
0
y
4
+
x
1
x
3
+
y
1
y
3
)
+
x
2
2
+
y
2
2
=
10
w
4
+
a
4
-
w
3
,
A
5
=
2
(
x
0
x
5
+
y
0
y
5
+
x
1
x
4
+
y
1
y
4
+
x
2
x
3
+
y
2
y
3
)
=
10
w
5
+
a
5
-
w
4
,
A
6
=
2
(
x
2
x
4
+
y
2
y
4
)
+
x
3
2
+
y
3
2
=
10
w
6
+
a
6
-
w
5
,
A
7
=
2
(
x
2
x
5
+
y
2
y
5
+
x
3
x
4
+
y
3
y
4
)
=
10
w
7
+
a
7
-
w
6
,
A
8
=
2
(
x
3
x
5
+
y
3
y
5
)
+
x
4
2
+
y
4
2
=
10
w
8
+
a
8
-
w
7
,
A
9
=
2
(
x
4
x
5
+
y
4
y
5
)
=
10
w
9
+
a
9
-
w
8
,
A
1
0
=
x
5
2
+
y
5
2
=
10
w
1
0
+
a
1
0
-
w
9
,
for
some
w
0
,
…
,
w
1
0
∈
{
0
,
1
,
…
,
16
}
.
Remark 4-2
Notice that aj represents the digital value and Bj represents a polynomial function for j=0, . . . , λ, they are closely related in the following way:
Proposition 7-2
For Bj specified in Remark 3-2, there exist w0, . . . , wλ∈{0, 1, . . . , 16} such that the following equations are true:
B
0
=
-
x
0
2
+
y
0
2
=
10
w
0
+
a
0
(
i
)
B
j
=
10
w
j
+
a
j
-
w
j
-
1
,
j
=
1
,
…
,
λ
-
1
(
ii
)
where Bj=2Σ(h,l)∈Sj(−xhxl+yhyl), when j is odd;
Bj=−xj/22+yj/22+2Σ(h,l)∈Sj(−xhxl+yhyl), when j is even;
and Sj={(h,l) integers: h+l=j, 0≤h<l≤λ/2}.
B
λ
=
-
x
λ
/
2
2
+
y
λ
/
2
2
=
1
0
w
λ
+
a
λ
-
w
λ
-
1
.
(
iii
)
Remark 4-3
Notice that aj represents the digital value and Cj represents a polynomial function for j=0, . . . , λ, they are closely related in the following way:
Proposition 7-3
For Cj specified in Remark 3-3, there exist w, . . . , wλ∈{0, 1, . . . , 16} such that the following equations are true:
C
0
=
x
0
2
+
y
0
2
=
10
w
0
+
a
0
,
(
i
)
C
j
=
10
w
j
+
a
j
-
w
j
-
1
,
j
=
1
,
…
,
λ
-
1
,
(
ii
)
where Cj=2Σ(h,l)∈Sj(xhxl−yhyl), when j is odd;
Cj=xj/22−yj/22+2Σ(h,l)∈Sj(xhxl−yhyl), when j is even;
and Sj={(h,l) integers: h+l=j, 0≤h<l≤λ/2}.
C
λ
=
x
λ
/
2
2
-
y
λ
/
2
2
=
10
w
λ
+
a
λ
-
w
λ
-
1
.
(
iii
)
Proposition 8-1:
For Aj specified in Proposition 7-1, given the values of (x0, y0, xλ/2, yλ/2), we can solve all Aj equations by linear integer programs effectively as follows:
(i) Given x0 and y0, we obtain
w
0
=
1
1
0
(
a
0
-
x
0
2
-
y
0
2
)
(ii) Given x0, y0, and w0 found in (i), we obtain the values of x1, y1 and w1 by solving the following linear integer program:
Min
.
w
1
subject
to
2
(
x
0
x
1
+
y
0
y
1
)
=
10
w
1
+
a
1
-
w
0
;
x
1
=
∑
s
=
0
9
s
×
u
1
s
;
y
1
=
∑
s
=
0
9
s
×
v
1
s
;
∑
s
=
0
9
u
1
s
=
1
;
∑
s
=
0
9
v
1
s
=
1
;
u
1
s
,
v
1
s
∈
{
0
,
1
0
,
0
≤
w
1
≤
16
,
w
1
∈
N
0
.
(iii) Given w1 found in (ii), we obtain the values of x2, y2 and w2 by solving the following linear integer program:
Min
.
w
2
subject
to
2
(
x
0
x
2
+
y
0
y
2
)
+
x
1
2
+
y
1
2
=
10
w
2
+
a
2
-
w
1
;
x
2
=
∑
s
=
0
9
s
×
u
2
s
;
y
2
=
∑
s
=
0
9
s
×
v
2
s
;
∑
s
=
0
9
u
2
s
=
1
;
∑
s
=
0
9
v
2
s
=
1
;
x
1
2
∑
s
=
0
9
S
2
×
u
2
s
;
y
1
2
=
∑
s
=
0
9
s
2
×
v
2
s
;
∑
s
=
0
9
u
1
s
=
1
;
∑
s
=
0
9
v
1
s
=
1
;
u
2
s
,
v
2
s
∈
{
0
,
1
}
,
0
≤
w
2
≤
16
,
w
2
∈
N
0
.
(iv) Similarly, by given the known wj, xj, yj, it can be found that xj+1, yj+1 and wj+1 for j=0, 1, 2, 3, . . . , λ.
Proposition 8-2:
For Bj specified in Proposition 7-2, given the values of (x0, y0, xλ/2, yλ/2), all Bj equations can be solved by similar linear integer programs in Proposition 8.1.
Proposition 8-3:
For Cj specified in Proposition 7-3, given the values of (x0, y0, xλ/2, yλ/2), we can solve all Cj equations by similar linear integer programs in Proposition 8.1.
Proposition 9-1
For a Type-1 semi-prime θ=(m2+n2 or m2+n2; m, m even, n, n odd),
If
a
0
=
1
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
0
,
1
2
)
,
(
0
,
9
2
)
,
(
4
2
,
5
2
)
,
(
6
2
,
5
2
)
}
.
(
i
)
If
a
0
=
3
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
2
2
,
3
2
)
,
(
2
2
,
7
2
)
,
(
8
2
,
3
2
)
,
(
8
2
,
7
2
)
}
.
(
ii
)
If
a
0
=
7
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
4
2
,
1
2
)
,
(
4
2
,
9
2
)
,
(
6
2
,
1
2
)
,
(
6
2
,
9
2
)
}
.
(
iii
)
If
a
0
=
9
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
0
,
3
2
)
,
(
0
,
7
2
)
,
(
2
2
,
5
2
)
,
(
8
2
,
5
2
)
}
.
(
iv
)
As listed in the second column of Table 1.
Proposition 9-2
For a Type-2 semi-prime θ=(n2−m2; n odd, m even,),
If
a
0
=
1
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
1
2
,
0
)
,
(
9
2
,
0
)
,
(
5
2
,
2
2
)
,
(
15
2
,
8
2
)
}
.
(
i
)
If
a
0
=
3
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
7
2
,
4
2
)
,
(
13
2
,
4
2
)
,
(
7
2
,
6
2
)
,
(
13
2
,
6
2
)
}
.
(
ii
)
If
a
0
=
7
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
9
2
,
2
2
)
,
(
11
2
,
2
2
)
,
(
9
2
,
8
2
)
,
(
11
2
,
8
2
)
}
.
(
iii
)
If
a
0
=
9
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
3
2
,
0
)
,
(
7
2
,
0
)
,
(
5
2
,
4
2
)
,
(
15
2
,
6
2
)
}
.
(
iv
)
As listed in the second column of Table 1.
Proposition 9-3
For a Type-3 semi-prime θ=(m2−n2; m even, n odd),
If
a
0
=
1
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
6
2
,
5
2
)
,
(
10
2
,
3
2
)
,
(
10
2
,
7
2
)
,
(
14
2
,
5
2
)
}
(
i
)
If
a
0
=
3
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
2
2
,
1
2
)
,
(
8
2
,
1
2
)
,
(
12
2
,
9
2
)
,
(
18
2
,
9
2
)
}
(
ii
)
If
a
0
=
7
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
4
2
,
3
2
)
,
(
6
2
,
3
2
)
,
(
14
2
,
2
)
,
(
16
2
,
7
2
)
}
(
iii
)
If
a
0
=
9
,
then
(
x
0
2
,
y
0
2
)
∈
{
(
8
2
,
5
2
)
,
(
10
1
,
1
2
)
,
(
10
2
,
9
2
)
,
(
12
2
,
5
2
)
}
(
iv
)
As listed in the second column of Table 1.
TABLE 1
Possible Values of (x0, y0)
θ = 4 k + 1 = m2 + n2
θ = 4 k + 1 = n2 − m2
θ = 4 k + 3 = m2 − n2
Even + Odd
Odd − Even
Even − Odd
α0
x02
y02
x02
y02
x02
y02
1
0
1
1
0
62
52
0
92
92
0
102
32
42
52
52
22
102
72
62
52
152
82
142
52
3
22
32
132
42
22
1
22
72
72
42
82
1
82
32
132
62
122
92
82
72
72
62
182
92
7
42
1
92
22
422
32
42
92
112
22
62
32
62
1
112
82
142
72
62
92
92
82
162
72
9
0
32
32
0
82
52
0
72
72
0
102
12
22
52
52
42
102
92
82
52
152
62
122
52
Proposition 10-1
Let θ be a Type-1 semi-prime that is the product of two 4k+1 primes. Then there exist positive integers m, m, n, n with m>m being even and n<n being odd, such that θ=m2+n2=m2+n2. Moreover, if it is denoted as:
α
=
1
2
gcd
(
m
-
m
¯
,
n
¯
-
n
)
;
β
=
1
2
gcd
(
m
+
m
¯
,
n
¯
+
n
)
;
α
¯
=
1
2
gcd
(
m
-
m
¯
,
n
¯
+
n
)
;
β
¯
=
1
2
gcd
(
m
+
m
¯
,
n
¯
-
n
)
;
then p=α2+β2 and p=α2+β2 are 4k+1 primes and θ=p×p.
Example: Given θ=221, we have θ=142+52=102+112. Moreover, α=1, β=4, α=2, β=3, and then p=12+42=17, p=22+32=13 are 4k+1 primes, and θ=221=17×13.
Proposition 10-2
Let θ be a Type-2 semi-prime, which is the product of two 4k+3 primes. Then there exist positive integers m<n with m being even and n being odd, such that
θ=−m2+n2. Moreover, if we denote
q=n+m and q=n−m then q and q are 4k+3 primes and θ=q×q.
Proposition 10-3
Let θ be a Type-3 semi-prime, which is the product of one 4k+1 prime and
one 4k+3 prime. Then there exist positive integers m>n with m being even and n being odd, such that θ=m2−n2. Moreover, if it is denoted:
p=m+n and q=m−n then p is a 4+1 prime and q is a 4k+3 prime and θ=p×q.
Next, for different types of the Semi-primes, methods 1, 2, 3 Are demonstrated to show the different ways of proceeding.
Method 1—Factorization of Type-1 Semi-Primes:
Input—Given any Type-i semi-prime
θ
=
∑
j
=
0
λ
a
j
×
1
0
j
where λ is even, 0≤aj≤9 for 0≤j≤λ−1, and 0≤aλ≤99.
Output—Two 4k+1 prime numbers p1 and p2 such that θ=p1×p2.
Subproblems corresponding to the combinations of a0 and aλ are generated.
Mixed-Integer Programming (MIP) Modeling:
Variables: for each subproblem w0, . . . , wλ∈{0, 1, . . . , 16}
x
0
∈
{
0
,
2
,
4
,
6
,
8
}
,
x
1
…
,
x
λ
/
2
∈
{
0
,
…
,
9
}
(
transitional
only
)
y
0
∈
{
1
,
3
,
5
,
7
,
9
}
,
y
1
…
,
y
λ
/
2
∈
{
0
,
…
,
9
}
(
transitional
only
)
u
h
s
∈
{
0
,
1
}
,
for
0
≤
h
≤
λ
/
2
,
s
∈
{
0
,
1
,
…
,
9
}
v
h
s
∈
{
0
,
1
}
,
for
0
≤
h
≤
λ
/
2
,
s
∈
{
0
,
1
,
…
,
9
}
x
(
h
,
l
)
≥
0
,
for
(
h
,
l
)
∈
S
j
,
j
=
1
,
…
,
λ
-
1
y
(
h
,
l
)
≥
0
,
for
(
h
,
l
)
∈
S
j
,
j
=
1
,
…
,
λ
-
1
Integer Equations for Each Subproblem:
A
0
=
x
0
2
+
y
0
2
=
10
w
0
+
a
0
,
A
j
=
2
∑
(
h
,
l
)
∈
S
j
(
x
h
x
l
+
y
h
y
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
1
≤
j
(
odd
)
≤
λ
-
1
A
j
=
x
j
/
2
2
+
y
j
/
2
2
+
2
∑
(
h
,
l
)
∈
S
j
(
x
h
x
l
+
y
h
y
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
1
≤
j
(
even
)
≤
λ
-
1
A
λ
=
x
λ
/
2
2
+
y
λ
/
2
2
=
10
w
λ
+
a
λ
-
w
λ
-
1
,
x
0
=
∑
s
=
0
,
2
,
4
,
6
,
8
s
×
u
0
s
,
x
h
=
∑
s
=
0
9
s
×
u
h
s
,
for
1
≤
h
≤
λ
/
2
,
x
h
2
=
∑
s
=
0
9
s
2
×
u
h
s
,
for
0
≤
h
≤
λ
/
2
,
∑
s
=
0
9
u
h
s
=
1
,
y
0
=
∑
s
=
1
,
3
,
5
,
7
,
9
s
×
v
0
s
,
y
h
=
∑
s
=
0
9
s
×
v
h
s
,
for
1
≤
h
≤
λ
/
2
,
y
h
2
=
∑
s
=
0
9
s
2
×
v
h
s
,
for
0
≤
h
≤
λ
/
2
,
∑
s
=
0
9
v
h
s
=
1
.
MIP Resolution: Solve the MIP model for each subproblem by an incremental approach in Proposition 8.1.
Optimization:
Step 1: Solve all subproblems to obtain two feasible solutions (x0, x1, . . . , xλ/2; y0, y1, . . . , yλ/2) and (x0, x1, . . . , xλ/2; y0, y1, . . . , yλ/2).
Step 2: Calculate
m
=
∑
j
=
0
λ
/
2
x
j
×
1
0
j
,
n
=
∑
j
=
0
λ
/
2
y
j
×
1
0
j
.
Step 3: Calculate
m
¯
=
∑
j
=
0
λ
/
2
x
¯
j
×
1
0
j
,
n
¯
=
∑
j
=
0
λ
/
2
y
¯
j
×
1
0
j
.
Step 4: Calculate
α
=
1
2
gcd
(
m
-
m
¯
,
n
¯
-
n
)
;
β
=
1
2
gcd
(
m
+
m
¯
,
n
¯
+
n
)
;
α
¯
=
1
2
gcd
(
m
-
m
¯
,
n
¯
+
n
)
;
β
¯
=
1
2
gcd
(
m
+
m
¯
,
n
¯
-
n
)
;
Step 5: Calculate p1=α2+β2 and p2=α2+β2
Step 6: Output θ=p1×p2
Method 2—Factorization of Type-2 Semi-Primes
Input—Given any Type-2 semi-prime
θ
=
∑
j
=
0
λ
a
j
×
1
0
j
where λ is even, 0≤aj≤9 for 0≤j≤λ−1, and 0≤aj≤99.
Output—Two 4k+3 primes q1 and q2 such that θ=q1×q2
Subproblems corresponding to the combinations of do and an are generated.
MIP Modeling:
Variables: For each subproblem, w0, . . . , w∈{0, 1, . . . , 16},
x
0
∈
{
0
,
2
,
4
,
6
,
8
}
,
x
1
,
,
x
λ
/
2
∈
{
0
,
…
,
9
}
(
transitional
only
)
,
y
0
∈
{
1
,
3
,
5
,
7
,
9
}
,
y
1
,
,
y
λ
/
2
∈
{
0
,
…
,
9
}
(
transitional
only
)
,
u
h
s
∈
{
0
,
1
}
,
for
0
≤
h
≤
λ
/
2
,
s
∈
{
0
,
1
,
…
,
9
}
,
v
h
s
∈
{
0
,
1
}
,
for
0
≤
h
≤
λ
/
2
,
s
∈
{
0
,
1
,
…
,
9
}
,
x
(
h
,
l
)
≥
0
,
for
(
h
,
l
)
∈
S
j
,
j
=
1
,
…
,
λ
-
1
,
y
(
h
,
l
)
≥
0
,
for
(
h
,
l
)
∈
S
j
,
j
=
1
,
…
,
λ
-
1.
Integer Equations for Each Subproblem:
B
0
=
-
x
0
2
+
y
0
2
=
10
w
0
+
a
0
,
B
j
=
2
∑
(
h
,
l
)
∈
S
j
(
-
x
h
x
l
+
y
h
y
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
1
≤
j
(
odd
)
≤
λ
-
1.
B
j
=
-
x
j
/
2
2
+
y
j
/
2
2
+
2
∑
(
h
,
l
)
∈
S
j
(
-
x
h
x
l
+
y
h
y
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
1
≤
j
(
even
)
≤
λ
-
1
,
B
λ
=
x
λ
/
2
2
+
y
λ
/
2
2
=
10
w
λ
+
a
λ
-
w
λ
-
1
,
x
0
=
∑
s
=
0
,
2
,
4
,
6
,
8
s
×
u
0
s
,
x
h
=
∑
s
=
0
9
s
×
u
0
s
,
for
1
≤
h
≤
λ
/
2
,
x
h
2
=
∑
s
=
0
9
s
2
×
u
0
s
,
for
0
≤
h
≤
λ
/
2
,
∑
s
=
0
9
u
0
s
=
1
,
y
0
=
∑
s
=
1
,
3
,
5
,
7
,
9
s
×
v
0
s
,
y
h
=
∑
s
=
0
9
s
×
v
h
s
,
for
1
≤
h
≤
λ
/
2
,
y
h
2
=
∑
s
=
0
9
s
2
×
v
h
s
,
for
0
≤
h
≤
λ
/
2
,
∑
s
=
0
9
v
h
s
=
1.
Optimization Model:
MILP Resolution: Solve the MIP for each subproblem by an incremental technique in Proposition 8.2.
Optimization:
Step 1: Solve all subproblems to get a solution x0, x1, . . . , xλ/2 and y0, y1, . . . , yλ/2.
Step 2: Calculate
m
=
∑
j
=
0
λ
/
2
x
j
×
1
0
j
,
n
=
∑
j
=
0
λ
/
2
y
j
×
1
0
j
.
Step 3: Calculate q1=n+m and q2=n−m.
Step 4: Output θ=q1×q2.
Method 3—Factorization of Type-3 Semi-Primes
Input—Given any Type-3 semi-prime
θ
=
∑
j
=
0
λ
a
j
×
1
0
j
where λ is even, 0≤aj≤9 for 0<j≤λ−1, and 0≤aλ≤99.
Output—One 4k+1 and one 4k+3 prime numbers p1 and q2 such that θ=p1×q2.
Subproblems corresponding to the combinations of do and an are generated.
MIP Modeling:
Variables: For each subproblem, w0, . . . , w2∈{0, 1, . . . , 16}
x
0
∈
{
0
,
2
,
4
,
6
,
8
}
,
x
1
,
,
x
λ
/
2
∈
{
0
,
…
,
9
}
(
transitional
only
)
,
y
0
∈
{
1
,
3
,
5
,
7
,
9
}
,
y
1
,
,
y
λ
/
2
∈
{
0
,
…
,
9
}
(
transitional
only
)
,
u
h
s
∈
{
0
,
1
}
,
for
0
≤
h
≤
λ
/
2
,
s
∈
{
0
,
1
,
…
,
9
}
,
v
h
s
∈
{
0
,
1
}
,
for
0
≤
h
≤
λ
/
2
,
s
∈
{
0
,
1
,
…
,
9
}
,
x
(
h
,
l
)
≥
0
,
for
(
h
,
l
)
∈
S
j
,
j
=
1
,
…
,
λ
-
1
,
y
(
h
,
l
)
≥
0
,
for
(
h
,
l
)
∈
S
j
,
j
=
1
,
…
,
λ
-
1.
Integer Equations for Each Subproblem:
C
0
=
x
0
2
-
y
0
2
=
10
w
0
+
a
0
C
j
=
2
∑
(
h
,
l
)
∈
S
j
(
x
h
x
l
-
y
h
y
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
1
≤
j
(
odd
)
≤
λ
-
1.
C
j
=
-
x
j
/
2
2
-
y
j
/
2
2
+
2
∑
(
h
,
l
)
∈
S
j
(
x
h
x
l
-
y
h
y
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
1
≤
j
(
even
)
≤
λ
-
1
,
C
λ
=
x
λ
/
2
2
-
y
λ
/
2
2
=
10
w
λ
+
a
λ
-
w
λ
-
1
,
x
0
=
∑
s
=
0
,
2
,
4
,
6
,
8
s
×
u
0
s
,
x
h
=
∑
s
=
0
9
s
×
u
h
s
,
for
1
≤
h
≤
λ
/
2
,
x
h
2
=
∑
s
=
0
9
s
2
×
u
h
s
,
for
0
≤
h
≤
λ
/
2
,
∑
s
=
0
9
u
h
s
=
1
,
y
0
=
∑
s
=
1
,
3
,
5
,
7
,
9
s
×
v
0
s
,
y
h
=
∑
s
=
0
9
s
×
v
h
s
,
for
1
≤
h
≤
λ
/
2
,
y
h
2
=
∑
s
=
0
9
s
2
×
v
h
s
,
for
0
≤
h
≤
λ
/
2
,
∑
s
=
0
9
v
h
s
=
1.
MILP Resolution: Solve the MIP for each subproblem by an incremental technique in Proposition 8.3.
Optimization:
Step 1: Solve all subproblems to get an optimal solution
x0, x1, . . . , xλ/2 and y0, y1, . . . , yλ/2.
Step 2: Calculate
m
=
∑
j
=
0
λ
/
2
x
j
×
1
0
j
,
n
=
∑
j
=
0
λ
/
2
y
j
×
1
0
j
.
Step 3: Calculate p1=m+n and q2=m−n.
Step 4: Output θ=p1×q2.
In the following descriptions, examples are used to illustrate some embodiments of the present invention.
Remark 5: For a Type-i semi-prime θ, denote Ti(θ) and Hi(θ) as the tail-and-head sets for (X, Y), specified as
T
1
(
θ
)
=
{
(
x
0
,
y
0
)
❘
"\[LeftBracketingBar]"
x
0
2
+
y
0
2
=
a
0
}
,
H
1
(
θ
)
=
{
(
x
λ
/
2
,
y
λ
/
2
)
❘
"\[LeftBracketingBar]"
x
λ
/
2
2
+
y
λ
/
2
2
≤
a
0
}
,
T
2
(
θ
)
=
{
(
x
0
,
y
0
)
❘
"\[LeftBracketingBar]"
x
0
2
-
y
0
2
=
a
0
}
,
H
2
(
θ
)
=
{
(
x
λ
/
2
,
y
λ
/
2
)
❘
"\[LeftBracketingBar]"
x
λ
/
2
2
+
y
λ
/
2
2
≤
a
λ
}
,
T
3
(
θ
)
=
{
(
x
0
,
y
0
)
❘
"\[LeftBracketingBar]"
x
0
2
-
y
0
2
=
a
0
}
,
H
3
(
θ
)
=
{
(
x
λ
/
2
,
y
λ
/
2
)
❘
"\[LeftBracketingBar]"
x
λ
/
2
2
-
y
λ
/
2
2
≤
a
λ
}
,
where 0<x0, y0≤9, 0≤xλ/2, yλ/2≤99, x0, y0, xλ/2, yλ/2∈N0.
A problem of factorizing a Type-i semi-primes θ can be divided into z subproblems, for z=|Ti(θ)|×|Hi(θ)|, where i is 1, 2, or 3. The algorithm for factorizing
θ
=
∑
j
=
0
λ
1
0
λ
a
j
as a product of two primes is illustrated in FIG. 2.
In FIG. 2, diagram of LIP algorithms for Type-i semi-prime θ is shown, from the block B102, there are three processes, including Type-1 Semi-primes at the block B104, Type-2 Semi-primes at the block B106, and Type-3 Semi-primes at the block B108. The block B102 represents
θ
=
∑
j
=
0
λ
a
j
×
1
0
λ
,
which is the first stage for the factorization.
The block B104, representing the Type-1 Semi-primes, contains:
Tail & Head: T1, H1.
Equations: A0, A1, . . . , Aλ/2.
Subproblems: SP1, SP2, . . . , SPz, z=|T1|×|H1|.
Feasible solutions: (X, Y), (X, Y).
θ
=
Σ
A
j
(
X
,
Y
)
×
10
j
=
Σ
A
j
(
X
_
,
Y
_
)
×
10
j
.
θ
=
p
×
p
=
(
α
2
+
β
2
)
(
α
_
2
+
β
_
2
)
.
α
=
1
2
gcd
(
m
-
m
_
,
n
_
-
n
)
,
β
=
1
2
gcd
(
m
+
m
_
,
n
_
+
n
)
.
α
=
gcd
(
m
-
m
_
,
n
_
+
n
)
,
β
=
gcd
(
m
+
m
_
,
n
_
-
n
)
.
m
=
∑
x
j
×
10
j
>
m
_
=
∑
x
_
j
×
10
j
,
n
=
∑
y
j
×
10
j
<
n
_
=
∑
y
_
j
×
10
j
.
A
0
=
x
0
2
+
y
0
2
=
10
ω
0
+
a
0
A
j
=
x
j
/
2
2
+
y
j
/
2
2
+
2
∑
h
+
l
=
j
(
r
h
,
l
+
z
h
,
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
j
is
even
.
A
j
=
2
∑
h
+
l
=
j
(
r
h
,
l
+
z
h
,
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
j
is
odd
.
A
λ
=
x
λ
/
2
2
+
y
λ
/
2
2
=
10
w
λ
+
a
λ
-
w
λ
-
1
The block B106, representing the Type-2 Semi-primes, contains:
Tail & Head: T2, H2.
Equations: B0, B1, . . . , Bλ/2.
Subproblems: SP1, SP2, . . . , SPz, z=|T2|×|H2|.
Feasible solutions: (X, Y).
θ
=
(
∑
y
j
×
10
j
)
2
-
(
∑
x
j
×
10
j
)
2
·
=
[
Σ
(
y
j
+
x
j
)
×
10
j
]
[
Σ
(
y
j
-
x
j
)
×
10
j
]
.
B
0
=
y
0
2
-
x
0
2
=
10
w
0
+
a
0
B
j
=
y
j
/
2
2
+
x
j
/
2
2
+
2
∑
(
z
h
,
l
+
r
h
,
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
j
is
even
.
B
j
=
2
∑
(
z
h
,
l
+
r
h
,
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
j
is
odd
.
B
λ
=
y
λ
/
2
2
+
x
λ
/
2
2
=
10
w
λ
+
a
λ
-
w
λ
-
1
The block B106, representing the Type-3 Semi-primes, contains:
Tail & Head: T3, H3.
Equations: C0, C1, . . . , Cλ/2.
Subproblems: SP1, SP2, . . . , SPz, z=|T3|×|H3|.
Feasible solutions: (X, Y).
θ
=
(
∑
x
j
×
10
j
)
2
-
(
∑
y
j
×
10
j
)
2
·
=
[
Σ
(
x
j
+
y
j
)
×
10
j
]
[
Σ
(
x
j
-
y
j
)
×
10
j
]
.
C
0
=
y
0
2
-
x
0
2
=
10
w
0
+
a
0
C
j
=
x
j
/
2
2
+
y
j
/
2
2
+
2
∑
(
r
h
,
l
+
z
h
,
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
j
is
even
.
C
j
=
2
∑
(
r
h
,
l
+
z
h
,
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
j
is
odd
.
C
λ
=
x
λ
/
2
2
+
y
λ
/
2
2
=
10
w
λ
+
a
λ
-
w
λ
-
1
In the above equations, xj=Σluj,l, yj=Σlvj,l, rh,l=xhxl, zh,l=yhyl, rh,l, zh,l∈{0, 1}. Further, the above equations are transformed into linear-integer-programming subproblems to be solved for finding exact solutions.
Example 5: Semi-prime θ=12,648,677,849 is to be factorized into the product of two primes. Since 0 is in the form of 4k+1, it is either the product of two Type-1 primes or the product of two Type-3 primes. Firstly, we suppose θ is the former. Since
θ
=
∑
j
=
0
1
0
a
j
×
1
0
j
,
we have (a10, a9, a8, . . . a0)=(1, 2, 6, 4, 8, 6, 7, 7, 8, 4, 9). The target θ is then factorized by Method 1 as follows. Since a0=9, referring to Table 1, we have (x0, y0)∈{(0,3), (0,7), (2,5), (8,5)}. Since a10=1, then
x
5
2
+
y
5
2
≤
1
,
which implies (x5, y5)∈{(0,0), (0,1), (1,0)}. The problem of factorizing θ into the product of two 4k+1 primes, can be decomposed as 4×3=12 subproblems SP1, SP2, . . . , SP12. The admissible (x0, y0, x5, y5) tuples for these subproblems are listed in Table 2.
TABLE 2
12 subproblems defined by x02 + y02 = 9 and x52 + y52 ≤ 1.
SP#
1
2
3
4
5
6
7
8
9
10
11
12
x0
0
0
0
0
0
0
2
2
2
8
8
8
y0
3
3
3
7
7
7
5
5
5
5
5
5
x5
0
0
1
0
0
1
0
0
1
0
0
1
y5
0
1
0
0
1
0
0
1
0
0
1
0
We take SP6 with (x0, y0, x5, y5)=(0, 7, 0, 1) as an example.
Step 0: Solving
A
0
=
x
0
2
+
y
0
2
=
0
+
4
9
=
1
0
w
0
+
9
,
we have w0=4.
Step 1: Solve
{Min w0, subject to 2(x0x1+y0y1)=14y1=10w1+4−4, 0≤w1≤16, 0≤x1, y1≤9} to obtain w1=0 and y1=0.
Solve
{Min w1, subject to 4y1=10w1, w1>0, 0≤y1≤9, 0≤w1≤16} to obtain w1=7 and y1=5.
Step 2: Given (w1=0, y1=0), solving
A
2
=
1
4
y
2
+
x
1
2
+
y
1
2
=
1
0
w
2
+
8
-
w
1
,
we obtain (x1, y2, w2)∈{(2, 1, 1), (0, 2, 2), (2, 6, 8), (0, 7, 9)}.
Given (w1=7, y1=5), we solve A2=10w2+8−w1 and obtain (x1, y2, w2)∈{(4, 0, 4), (6, 0, 6), (2, 3, 7), (0, 4, 8)}.
Step 3: Given (x1, y2, w2), solving A3=14y3+2x1x2+2y1y2=10w3+7−w2, we find that there is no feasible solution.
Given (x1, y2, w2)=(0, 7, 9), we solve A3 and obtain (y3, w3)=(7, 10).
Step 4: Given (y3, w3)=(7,10), solving
A
4
=
14
y
4
+
2
x
1
x
3
+
2
y
1
y
3
+
x
2
2
+
y
2
2
=
10
w
4
+
7
-
w
3
,
we find (x2, y4, w4)=(0, 2, 8) among the solutions. Use this solution to solve
A
5
=
14
y
5
+
2
x
1
x
4
+
2
y
1
y
4
+
2
x
2
x
3
+
y
2
y
3
=
10
w
5
+
6
-
w
4
and find w5=10. This solution is further used to solve
A
6
=
2
x
2
x
4
+
2
y
2
y
4
+
x
3
2
+
y
3
2
=
10
w
6
+
8
-
w
5
and we find (x3, w6)=(9,16) among the solutions. Further, we solve
A
7
=
2
x
3
x
4
+
2
y
3
y
4
=
10
w
7
+
4
-
w
6
and find (x4, w7)=(0,4) among the solutions. Then, we solve
A
8
=
2
x
3
+
x
4
2
+
y
4
2
=
10
w
8
+
6
-
w
7
.
(y4, w8)=(2,2) is one of the solutions. Using this solution, we solve
A
9
=
2
x
4
=
10
w
9
+
2
-
w
8
.
to find the solution w9=0. The last equation is solved:
A
10
=
1
=
10
w
10
+
1
-
w
9
.
We obtain w10=0.
Therefore, we conclude that subproblem SP6 has a feasible solution.
(
x
1
,
x
2
,
x
3
,
x
4
;
y
1
,
y
2
,
y
3
,
y
4
)
=
(
0
,
0
,
9
,
0
,
0
,
7
,
7
,
2
)
.
(
w
0
,
w
1
,
w
2
,
w
3
,
…
,
w
10
)
=
(
4
,
0
,
9
,
10
,
8
,
10
,
16
,
4
,
2
,
0
,
0
)
.
u
1
,
0
=
u
2
,
0
=
u
3
,
9
=
u
4
,
0
=
1
,
v
1
,
0
=
v
2
,
7
=
v
3
,
7
=
v
4
,
2
=
1
,
r
1
,
1
=
r
1
,
2
=
r
1
,
3
=
r
1
,
4
=
r
2
,
2
=
r
2
,
3
=
r
2
,
4
=
0
;
r
3
,
3
=
81
,
r
3
,
4
=
0
,
r
4
,
4
=
0
,
z
2
,
2
=
49
,
z
2
,
3
=
49
,
z
2
,
4
=
14
,
z
3
,
3
=
49
,
z
3
,
4
=
14
,
z
4
,
4
=
4.
Therefore we have:
(
10
5
x
5
+
10
4
x
4
+
10
3
x
3
+
10
2
x
3
+
10
2
x
2
+
10
x
1
+
x
0
)
2
+
(
10
5
y
5
+
10
4
y
4
+
10
3
y
3
+
10
2
y
2
+
10
y
1
+
y
0
)
2
=
10900
2
+
27707
2
=
12
,
648
,
677
,
849
=
θ
.
Step 5: In a similar way, solving all other 11 subproblems shown in Table 2. We then find that SP4 with (x0, y0, x5, y5)=(0, 7, 0, 0) has a feasible solutions as (x5, x4, x3, x2, x1; y5, y4, y3, y2, y1)=(0, 7, 0, 4, 0, 0; 0, 8, 7, 7, 0, 7).
That implies 704002+877072=12,648,677,849.
While all other 10 subproblems have no feasible solution, from the propositions, we have θ=109002+277072=704002+877072=(3002+1932)(1002+2992)=127449×99401.
Example 6: Consider semi-prime θ=1311413. We express θ as θ=1×106+3×105+1×104+1×103+4×102+1×102+3, where (a6, a5, a4, a3, a2, a1, a0)=(1, 3, 1, 1, 4, 1, 3).
Since θ=4k+1, we first assume that 0 is the product of two 4k+1 prime. No feasible solutions are attainable. We then factorize θ by Proposition 2 in the following equations.
A
0
=
y
0
2
-
x
0
2
=
10
w
0
+
3
,
A
1
=
2
(
y
0
y
1
-
x
0
x
1
)
=
10
w
1
+
1
-
w
0
,
A
2
=
2
(
y
0
y
2
-
x
0
x
2
)
+
y
1
2
-
x
1
2
=
10
w
2
+
4
-
w
1
,
A
3
=
2
(
y
0
y
3
-
y
1
y
2
-
x
0
x
3
-
x
1
x
2
)
=
10
w
3
+
1
-
w
2
,
A
4
=
2
(
y
0
y
4
-
y
1
y
3
-
x
0
x
4
-
x
1
x
3
)
+
y
2
2
-
x
2
2
=
10
w
4
+
1
-
w
3
,
A
5
=
2
(
y
2
y
3
-
x
2
x
3
)
=
10
w
5
+
3
-
w
4
,
A
6
=
y
3
2
-
x
3
2
=
10
w
6
+
1
-
w
5
.
Solving there equations by giving y0∈{3, 7} and x0∈{4, 6} referring to column 2 of Table 1. We obtain a solution below.
(
w
0
,
w
1
,
w
2
,
w
3
,
w
4
,
w
5
,
w
6
)
=
(
-
1
,
0
,
1
,
0
,
1
,
0
,
0
)
,
(
y
3
,
y
2
,
y
1
,
y
0
;
x
3
,
x
2
,
x
1
,
x
0
)
=
(
1
,
1
,
7
,
3
;
0
,
2
,
5
,
4
)
.
Therefore, we have
θ
=
1311413
=
(
n
+
m
)
(
n
-
m
)
=
n
2
-
m
2
=
(
1173
)
2
-
(
254
)
2
=
1427
×
919.
Example 7 Consider θ=181,807. Since θ=4k+3, it is the product of one 4k+1 prime and one 4k+3 prime. θ=18×104+1×103+8×102+7. By Proposition 3, we can rewritten as
θ
=
(
x
3
×
10
3
+
x
2
×
10
2
+
x
1
×
10
+
x
0
)
2
-
(
y
3
×
10
3
+
y
2
×
10
2
+
y
1
×
10
+
y
0
)
2
.
The following linear equations follow.
B
0
=
x
0
2
-
y
0
2
=
10
w
0
+
7
,
B
1
=
2
(
x
0
x
1
-
y
0
y
1
)
=
10
w
1
+
0
-
w
0
,
B
2
=
2
(
x
0
x
2
-
y
0
y
2
)
+
x
1
2
-
y
1
2
=
10
w
2
+
8
-
w
1
A
3
=
2
(
x
0
x
3
-
x
1
x
2
-
y
0
y
3
-
y
1
y
2
)
=
10
w
3
+
1
-
w
2
A
4
=
2
(
x
1
x
3
-
y
1
y
3
)
+
x
2
2
-
y
2
2
=
10
w
4
+
18
-
w
3
Solving the problem we obtain (w0, w1, w2, w3, w4)=(0, 0, −1, 3, 0) and (x3, x2, x1, x0; y3, y2, y1, y0)=(0, 4, 6, 4; 0, 1, 8, 3).
Therefore, we have
θ
=
181807
=
(
m
+
n
)
(
m
-
n
)
=
m
2
-
n
2
=
464
2
-
183
2
=
647
×
128.
Example 8: We consider a larger semi-prime
θ
=
100000
49610
15119
81129
=
∑
j
=
0
2
0
a
j
1
0
j
.
Since θ is a 4k+1 semi-prime, we first assume that it is the product of two Type-1 primes. Following Proposition 8.1 1 and Table 1 (column 1), we have θ=(1010x10+109x9+ . . . +x0)2+(1010y10+109y9+ . . . +y0)2, where (x0, y0)∈{(0,3), (0,7), (2,5), (8,5)}, (x10, y10)∈{(0,0), (0,1), (1,0)}, and (a20, a19, . . . a0)=(1, 0, 0, 0, 0, 0, 4, 9, 6, 1, 0 0, 5, 1, 1, 9 8, 1, 1, 2, 9).
The factorization problem can be divided into 4×3=12 subproblems. Each of three subproblems is formed as an integer program with 20 linear equations and some inequities as listed below:
Minimize
w
0
+
w
1
+
…
+
w
20
A
0
=
x
0
2
+
y
0
2
=
10
w
+
9
,
A
1
=
2
(
r
0
,
1
+
z
0
,
1
)
=
2
-
w
1
,
A
2
=
2
(
r
0
,
2
+
z
0
,
2
)
+
r
1
,
1
+
z
1
,
1
=
1
-
w
2
,
A
3
=
2
(
r
0
,
3
+
z
0
,
3
+
r
1
,
2
+
z
1
,
2
)
=
1
-
w
3
,
A
4
=
2
(
r
0
,
4
+
z
0
,
4
+
r
1
,
3
+
z
1
,
3
)
+
r
2
,
2
+
z
2
,
2
=
8
-
w
4
,
A
5
=
2
(
r
0
,
5
+
z
0
,
5
+
r
1
,
4
+
z
1
,
4
+
r
2
,
3
+
z
2
,
3
)
=
9
-
w
5
,
A
6
=
2
(
r
0
,
6
+
z
0
,
6
+
r
1
,
5
+
z
1
,
5
+
r
2
,
4
+
z
2
,
4
)
+
r
3
,
3
+
z
3
,
3
=
1
-
w
6
,
A
7
=
2
(
r
0
,
7
+
z
0
,
7
+
…
+
r
3
,
4
+
z
3
,
4
)
+
r
3
,
3
+
z
3
,
3
=
1
-
w
7
,
A
8
=
2
(
r
0
,
8
+
z
0
,
8
+
…
+
r
3
,
5
+
z
3
,
5
)
+
r
4
,
4
+
z
4
,
4
=
5
-
w
8
,
A
9
=
2
(
r
0
,
9
+
z
0
,
9
+
…
+
r
4
,
5
+
z
4
,
5
)
=
10
w
9
+
0
-
w
9
,
A
10
=
2
(
r
0
,
10
+
z
0
,
10
+
…
+
r
4
,
6
+
z
4
,
6
)
=
10
w
10
+
0
-
w
10
,
A
11
=
2
(
r
1
,
10
+
z
1
,
10
+
r
2
,
9
+
z
2
,
9
+
…
+
r
5
,
6
+
z
5
,
6
)
=
10
w
11
+
1
-
w
11
,
A
12
=
2
(
r
2
,
10
+
z
2
,
10
+
r
3
,
9
+
z
3
,
9
+
…
+
r
5
,
7
+
z
5
,
7
)
+
r
6
,
6
+
z
6
,
6
=
10
w
12
+
6
-
w
12
,
A
13
=
2
(
r
3
,
10
+
z
3
,
10
+
r
4
,
9
+
z
4
,
9
+
…
+
r
6
,
7
+
z
6
,
7
)
=
10
w
13
+
9
-
w
13
,
A
14
=
2
(
r
4
,
10
+
z
4
,
10
+
r
5
,
9
+
z
5
,
9
)
+
r
7
,
9
+
z
7
,
9
=
10
w
14
+
4
-
w
14
,
A
15
=
2
(
r
5
,
10
+
z
5
,
10
+
r
6
,
9
+
z
6
,
9
+
r
7
,
8
+
z
7
,
8
)
=
10
w
15
+
0
-
w
15
,
A
16
=
2
(
r
6
,
10
+
z
6
,
10
+
r
7
,
9
+
z
7
,
9
)
+
r
8
,
8
+
z
8
,
8
=
10
w
16
+
0
-
w
16
,
A
17
=
2
(
r
7
,
10
+
z
7
,
10
+
r
8
,
9
+
z
8
,
9
)
=
10
w
17
+
0
-
w
17
,
A
18
=
2
(
r
8
,
10
+
z
8
,
10
)
+
r
9
,
9
+
z
9
,
9
=
10
w
18
+
0
-
w
18
,
A
19
=
2
(
r
9
,
10
+
z
9
,
10
)
=
10
w
19
+
0
-
w
19
,
A
20
=
r
10
,
10
+
z
10
,
10
=
10
w
20
+
1
-
w
20
,
where for all feasible h, l,
x
h
=
∑
l
=
1
9
l
×
u
h
,
l
,
∑
l
=
0
9
u
h
,
l
=
1
;
(
i
)
y
h
=
∑
l
=
1
9
l
×
v
h
,
l
,
∑
l
=
0
9
v
h
,
l
=
1
;
(
ii
)
9
(
u
h
,
l
-
1
)
+
lx
l
≤
r
h
,
l
≤
lx
l
+
9
(
1
-
u
h
,
l
)
,
0
≤
r
h
,
l
≤
9
x
l
(
iii
)
9
(
u
h
,
l
-
1
)
+
ly
l
≤
z
h
,
l
≤
ly
l
+
9
(
1
-
v
h
,
l
)
,
0
≤
z
h
,
l
≤
9
y
l
(
iv
)
u
h
,
l
,
v
h
,
l
∈
{
0
,
1
}
,
x
h
,
y
h
,
r
h
,
l
,
z
h
,
l
≥
0.
For the subproblem with (x0, y0, x10, y10)=(0, 7, 0, 1), solving the subproblem by a commercial integer programming software we obtain the following solution:
(x10, x9, . . . x0)=(0, 0, 0, 0, 6, 6, 0, 0, 0, 0, 0),
(y10, y9, . . . y0)=(1, 0, 0, 0, 0, 0, 2, 2, 6, 2, 7)
(w0, w1, . . . w20)=(4, 3, 9, 6, 7, 3, 3, 1, 0, 0, 5, 8, 5, 0, 0, 0, 0, 0, 0, 0, 0).
It readily implies θ=66000002+100000226272.
For the subproblem with (x0, y0, x10, y10)=(0, 3, 0, 0), solving the subproblem we obtain
(x10, x9, . . . x0)=(0, 0, 0, 0, 3, 0, 8, 0, 0, 0, 0, 0),
(y10, y9, . . . y0)=(0, 9, 9, 9, 9, 9, 7, 7, 3, 7, 3),
which together implies θ=308000002+99999773732.
Therefore, we conclude that
θ
=
(
10
10
+
121
2
)
(
10
10
+
187
2
)
=
(
100000
14641
)
×
(
100000
34969
)
=
100000
49610
05119
81129.
In the case that no feasible solution exists when factorizing θ by assuming the product of two type-(4k+1) primes. Then, we follow Proposition 8.3 to factorize θ, since it is the product of two type-(4k+3) primes.
Example 9: Consider a large factorization problem marked as RSA-100 which has a decimal value of 100. That is θ=1522 . . . 139. LIP method factorizes θ as follows:
(i) Checking θ to know it is a 4k+3 semi-primes, therefore θ is the product of. one 4k+1 prime and one 4k+3 prime. We then denote θ as below by
Proposition 8.3:
θ
=
m
2
-
n
2
=
(
x
50
10
50
+
x
49
10
49
+
…
+
10
x
1
+
x
0
)
2
=
(
y
50
10
50
+
y
40
10
49
+
…
+
10
y
1
+
x
0
)
(ii) Since a0=9 and a100=1, we have
(x0, y0)∈{(8,5), (12,5), (10,1), (10,9)},
(x50, y50)∈{(1,0), (0,0)}.
(iii) Solving the binary program by a commercial integer program software to obtain the solution as
m
2
=
(
x
50
10
50
+
x
49
10
49
+
…
+
x
0
)
2
=
(
3903496444
3937277976
7463040241
0354812189
0218231130
)
,
n
2
=
(
x
50
10
50
+
x
49
10
49
+
…
+
y
0
)
2
=
(
0095993650
6983604053
9374312686
5792026732
4681492931
)
,
(iv) LIP then factorize θ as
θ
=
(
∑
j
=
0
50
x
j
10
j
+
∑
j
=
0
50
y
j
10
j
)
×
(
∑
j
=
0
50
x
j
10
j
-
∑
j
=
0
50
y
j
10
j
)
=
(
m
+
n
)
(
m
-
n
)
=
(
4009469095
0920881030
6837352927
6146838921
4899724061
)
×
(
3797522793
6943673922
8088727554
4562785456
5536638199
)
The factorization result is exactly the solution.
According to the above, the system 100 can a method for reducing computer processing time during private key decryption during digital communication, which is via performing operations using linear integer programming for RSA factorization as illustration in FIG. 3, including stages S102, S104, S106, S108, S110, S112, S114, S116, S118, S120, S122, S124, S126, S128, S130, S132, S134, S136, and S138.
In stage S102, a semi-prime θ is entered. For example, the semi-prime θ can be extracted by the n/e extractor from the public key and then is fed into the prime factorization calculator.
In stage S104, the semi-prime θ is defined and expressed as
θ
=
∑
j
=
0
λ
a
j
×
1
0
j
,
λ is an even number, aj∈{0, 1, . . . , 9}, j=0, 1, . . . , λ−1, aλ∈{0, 1, . . . , 99}.
In stage S106, the goal is to determine if semi-prime θ is in the form of a prime number of a type 4k+1 (i.e., is θ a 4k+1 prime?). If it is true, the next stage is S108 for processing in a first mode; otherwise, the next stage is S128 for processing in a third mode.
In stage S108, the semi-prime θ is expressed as:
θ
=
m
2
+
n
2
=
(
∑
j
=
0
λ
/
2
x
j
×
1
0
j
)
2
+
(
∑
j
=
0
λ
/
2
y
j
×
1
0
j
)
2
,
where x0 is even, y0 is odd; (ii) x0, x1, . . . , xλ/2, y0, y1, . . . , yλ/2∈{0, 1, . . . , 9}. For example, stage S108 includes:
expressing
θ
as
θ
=
m
2
+
n
2
(
m
=
∑
j
=
0
λ
2
x
j
×
10
j
even
,
n
=
∑
j
=
0
λ
2
y
j
×
10
j
odd
,
x
0
∈
{
0
,
2
,
4
,
6
,
8
}
,
x
1
,
x
2
,
…
,
x
λ
2
∈
{
0
,
1
,
,
9
}
;
y
0
∈
{
1
,
3
,
5
,
7
,
9
}
,
y
1
,
y
2
,
,
y
λ
/
2
∈
{
0
,
1
,
…
,
9
}
;
)
In stage S110, the main problem is decomposed into subproblems according
x
0
2
+
y
0
2
≡
a
0
(
mod
10
)
and
x
λ
/
2
2
+
y
λ
/
2
2
≤
a
λ
.
For example, stage S110 includes decomposing the main problem into subproblems, according to:
x
0
2
+
y
0
2
≡
a
0
(
mod
10
)
and
x
λ
/
2
2
+
y
λ
/
2
2
≤
a
λ
In stages S110 and S112, the prime factorization calculator can start to use a tail digit and a head digit set of the semi-prime number of the modulus to perform decomposition and factorization with respect to the semi-prime number into two prime factors via the first mode. The tail digit represents the last or least significant digit of the semi-prime number, and the head digit set represents the first two or most significant digits of the semi-prime number. For example, stage S112 includes: formulating each subproblem, given the corresponding (x0, y0, xλ/2, yλ/2), as an LIP problem as follows:
Minimize
∑
j
=
0
λ
-
1
w
j
subject
to
A
0
=
x
0
2
+
y
0
2
=
1
0
w
0
+
a
0
,
A
j
=
∑
h
+
l
=
j
,
h
,
l
∈
{
0
,
1
,
…
,
λ
/
2
}
(
r
h
,
l
+
z
h
,
l
)
=
1
0
w
j
+
a
j
-
w
j
-
1
,
1
≤
j
≤
λ
-
1
,
A
λ
=
x
λ
/
2
2
+
y
λ
/
2
2
=
a
λ
-
w
λ
-
1
,
w
0
,
…
,
w
λ
∈
ℕ
,
x
0
=
∑
s
=
0
,
2
,
4
,
6
,
8
s
×
u
0
s
,
x
h
=
∑
s
=
0
9
s
×
u
h
s
,
h
∈
{
1
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
2
,
…
,
λ
/
2
}
,
∑
s
=
0
9
u
h
s
=
1
,
u
h
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
,
h
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
,
y
0
=
∑
s
=
1
,
3
,
5
,
7
,
9
s
×
v
0
s
,
y
h
=
∑
s
=
0
9
s
×
v
h
s
,
h
∈
{
1
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
2
,
…
,
λ
/
2
}
,
∑
s
=
0
9
v
h
s
=
1
,
v
h
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
,
h
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
100
(
u
h
s
-
1
)
+
s
x
l
≤
r
h
,
l
,
100
(
1
-
u
h
s
)
+
sx
l
≥
r
h
,
l
,
r
h
,
l
∈
ℕ
,
h
,
l
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
100
(
v
h
s
-
1
)
+
s
y
l
≤
z
h
,
l
,
100
(
1
-
v
h
s
)
+
sy
l
≥
z
h
,
l
,
z
h
,
l
∈
ℕ
,
h
,
l
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
In stage S114, the prime factorization calculator can determine if two solutions
(
x
0
i
,
…
,
x
λ
2
i
,
y
0
j
,
…
,
y
λ
2
j
)
,
i
=
1
,
2
can be solved/obtained from the subproblems as above. If it is true, the next stage is S116 and it is processed via the first mode; otherwise, the next stage is S120 and the processes is switched to a second mode.
In stage S116, the prime factorization calculator can continue to perform factorization with respect to the semi-prime number into two prime factors p1 and p2 via the first mode. For example, stage S116 includes:
Calculating
m
i
=
∑
j
=
0
λ
/
2
x
j
i
×
1
0
j
,
n
i
=
∑
j
=
0
λ
/
2
y
j
i
×
1
0
j
,
i
=
1
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
2
,
m
1
>
m
2
,
n
1
<
n
2
α
=
1
2
gcd
(
m
1
-
m
2
,
n
2
-
n
1
)
;
β
=
1
2
g
c
d
(
m
1
+
m
2
,
n
2
+
n
1
)
;
α
¯
=
1
2
g
c
d
(
m
1
-
m
2
,
n
2
+
n
1
)
;
β
¯
=
1
2
g
c
d
(
m
1
+
m
2
,
n
2
-
n
1
)
;
p
1
=
α
2
+
β
2
,
p
2
=
α
_
2
+
β
¯
2
In stage S118, p1 and p2 are outputted from the prime factorization calculator 120 to the private key determiner 130. Then, it is to determine a private key using the public key exponent and the two prime numbers and then decrypt an encrypted message using the private key, thereby generating a decrypted message.
In stage S120, the semi-prime θ is expressed as:
θ
=
n
2
-
m
2
=
(
Σ
j
=
0
λ
2
y
j
×
1
0
j
)
2
-
(
Σ
j
=
0
λ
/
2
x
j
×
1
0
j
)
2
,
where x0 is even, y0 is odd; (ii) x0, x1, . . . , xλ/2, y0, y1, . . . , yλ/2∈{0, 1, . . . , 9}. For example, stage S120 includes: expressing θ as θ=n2−m2
(
m
=
∑
j
=
0
λ
2
x
j
×
1
0
j
even
,
n
=
∑
j
=
0
λ
2
y
j
×
1
0
j
odd
,
x
0
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
2
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
4
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
6
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
8
}
,
x
1
,
x
2
,
…
,
x
λ
2
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
;
y
0
∈
{
1
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
3
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
5
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
7
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
9
}
,
y
1
,
y
2
,
…
,
y
λ
/
2
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
)
In stages S122, S124, S126, and S128, the prime factorization calculator can use a tail digit and a head digit set of the semi-prime number of the modulus to perform decomposition and factorization with respect to the semi-prime number into two prime factors via the second mode. The main problem is decomposed into subproblems according to
-
x
0
2
+
y
0
2
≡
a
0
(
mod
10
)
and
-
x
λ
/
2
2
+
y
λ
/
2
2
≤
a
λ
.
A solution
(
x
0
,
…
,
x
λ
2
,
y
0
,
…
,
y
λ
2
)
can be obtained from subproblems.
For example, stage S122 includes decomposing the main problem into subproblems, according to:
-
x
0
2
+
y
0
2
≡
a
0
(
mod
10
)
and
-
x
λ
/
2
2
+
y
λ
/
2
2
≤
a
λ
.
For example, stage S124 includes: formulating each subproblem, given the corresponding (x0, y0, xλ/2, yλ/2), as an LIP problem as follows:
Minimize
∑
j
=
0
λ
-
1
w
j
subject
to
B
0
=
-
x
0
2
+
y
0
2
=
1
0
w
0
+
a
0
,
B
j
=
∑
h
+
l
=
j
,
h
,
l
∈
{
0
,
1
,
…
,
λ
/
2
}
(
-
r
h
,
l
+
z
h
,
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
1
≤
j
≤
λ
-
1
,
B
λ
=
x
λ
/
2
2
+
y
λ
/
2
2
=
a
λ
-
w
λ
-
1
,
w
0
,
…
,
w
λ
∈
ℕ
,
x
0
=
∑
s
=
0
,
2
,
4
,
6
,
8
s
×
u
0
s
,
x
h
=
∑
s
=
0
9
s
×
u
h
s
,
h
∈
{
1
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
2
,
…
,
λ
/
2
}
,
∑
s
=
0
9
u
h
s
=
1
,
u
h
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
,
h
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
,
y
0
=
∑
s
=
1
,
3
,
5
,
7
,
9
s
×
v
0
s
,
y
h
=
∑
s
=
0
9
s
×
v
h
s
,
h
∈
{
1
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
2
,
…
,
λ
/
2
}
,
∑
s
=
0
9
v
h
s
=
1
,
v
h
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
,
h
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
100
(
u
h
s
-
1
)
+
s
x
l
≤
r
h
,
l
,
100
(
1
-
u
h
s
)
+
sx
l
≥
r
h
,
l
,
r
h
,
l
∈
ℕ
,
h
,
l
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
100
(
v
h
s
-
1
)
+
s
y
l
≤
z
h
,
l
,
100
(
1
-
v
h
s
)
+
sy
l
≥
z
h
,
l
,
z
h
,
l
∈
ℕ
,
h
,
l
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
For example, stage S126 includes:
obtaining a solution (x0, . . . , xλ/2; y0, . . . , yλ/2) from the subproblems.
For example, stage S128 includes:
c
alculating
m
=
∑
j
=
0
λ
/
2
x
j
×
1
0
j
,
n
=
∑
j
=
0
λ
/
2
y
j
×
1
0
j
,
q
1
=
n
+
m
,
q
2
=
n
-
m
Then, it goes to stage S118 for outputting, q1 and q2.
In stage S130, the semi-prime θ is expressed as:
θ
=
m
2
-
n
2
=
(
∑
j
=
0
λ
/
2
x
j
×
1
0
j
)
2
-
(
∑
j
=
0
λ
/
2
y
j
×
1
0
j
)
2
,
where x0 is even, y0 is odd; (ii) x0, x1, . . . , xλ/2, y0, y1, . . . , yλ/2∈{0, 1, . . . , 9}. For example, stage S130 includes:
expressing
θ
as
θ
=
m
2
-
n
2
(
m
=
∑
j
=
0
λ
/
2
x
j
×
1
0
j
even
,
n
=
∑
j
=
0
λ
/
2
y
j
×
1
0
j
odd
,
x
0
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
2
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
4
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
6
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
8
}
,
x
1
,
x
2
,
…
,
x
λ
/
2
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
;
y
0
∈
{
1
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
3
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
5
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
7
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
9
}
,
y
1
,
y
2
,
…
,
y
λ
/
2
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
)
In stage S132, S134. S136, S138, the prime factorization calculator can use a tail digit and a head digit set of the semi-prime number of the modulus to perform decomposition and factorization with respect to the semi-prime number into two prime factors via the third mode. The main problem is decomposed into subproblems according to
x
0
2
-
y
0
2
≡
a
0
(
mod
0
)
and
x
λ
/
2
2
-
y
λ
/
2
2
≤
a
λ
.
A solution
(
x
0
,
…
,
x
λ
2
,
y
0
,
…
,
y
λ
2
)
can be obtained from subproblems.
For example, stage S132 includes decomposing the main problem into subproblems, according to:
x
0
2
-
y
0
2
≡
a
0
(
mod
10
)
and
x
λ
/
2
2
-
y
λ
/
2
2
≤
a
λ
For example, stage S134 includes: formulating each subproblem, given the corresponding (x0, y0, xλ/2, yλ/2), as an LIP problem as follows:
Minimize
∑
j
=
0
λ
-
1
w
j
subject
to
C
0
=
x
0
2
-
y
0
2
=
1
0
w
0
+
a
0
,
C
j
=
∑
h
+
l
=
j
,
h
,
l
∈
{
0
,
1
,
…
,
λ
/
2
}
(
r
h
,
l
-
z
h
,
l
)
=
10
w
j
+
a
j
-
w
j
-
1
,
1
≤
j
≤
λ
-
1
,
C
λ
=
x
λ
/
2
2
-
y
λ
/
2
2
=
a
λ
-
w
λ
-
1
,
w
0
,
…
,
w
λ
∈
ℕ
,
x
0
=
∑
s
=
0
,
2
,
4
,
6
,
8
s
×
u
0
s
,
x
h
=
∑
s
=
0
9
s
×
u
h
s
,
h
∈
{
1
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
2
,
…
,
λ
/
2
}
,
∑
s
=
0
9
u
h
s
=
1
,
u
h
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
,
h
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
,
y
0
=
∑
s
=
1
,
3
,
5
,
7
,
9
s
×
v
0
s
,
y
h
=
∑
s
=
0
9
s
×
v
h
s
,
h
∈
{
1
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
2
,
…
,
λ
/
2
}
,
∑
s
=
0
9
v
h
s
=
1
,
v
h
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
,
h
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
100
(
u
h
s
-
1
)
+
s
x
l
≤
r
h
,
l
,
100
(
1
-
u
h
s
)
+
sx
l
≥
r
h
,
l
,
r
h
,
l
∈
ℕ
,
h
,
l
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
100
(
v
h
s
-
1
)
+
s
y
l
≤
z
h
,
l
,
100
(
1
-
v
h
s
)
+
sy
l
≥
z
h
,
l
,
z
h
,
l
∈
ℕ
,
h
,
l
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
λ
/
2
}
,
s
∈
{
0
,
TagBox[",", "NumberComma", Rule[SyntaxForm, "0"]]
1
,
…
,
9
}
For example, stage S136 includes:
obtaining a solution (x0, . . . , xλ/2; y0, . . . , yλ/2) from the subproblems.
For example, stage S138 includes:
c
alculating
m
=
∑
j
=
0
λ
2
x
j
×
1
0
j
,
n
=
∑
j
=
0
λ
2
y
j
×
1
0
j
,
p1=m+n, q2=m−n
Then, it goes to stage S118 for outputting, p1 and q2.
Herein, in the first mode, the two prime factors are determined as a form of 4m+1 and 4n+1, where m and n are different positive integers; in the second mode, the two prime factors are determined as a form of 4m+3 and 4n+3, where m and n are different positive integers; and, in the third mode, the two prime factors are determined as a form of 4m+1 and 4n+3, where m and n are different positive integers. Furthermore, in one embodiment, there are only three modes.
Table 3 shows the comparison of the LIP method of the present invention with existing RSA methods. To factorize a semi-prime number θ in λ+2 (λ is even) digits, LIP uses decimals a0, a1, . . . , aλ to construct constraint equations. Currently available RSA methods neglect to utilize these valuable decimals in their algorithms. Table 3 also indicates that LIP is an optimization-based approach, which is guaranteed to factorize θ into two prime factors, while other RSA methods are heuristic approach-based, which need to specify some parameters according to the property of θ and may not converge to a feasible solution. The systems and methods presented in the present invention for performing operations using linear integer programming for RSA factorization can significantly reduce the computer processing time as well as power consumption, required for private key decryption during digital communication. In one embodiment, employing the LIP Method provided by the present invention, the computer processing time for private key decryption can be reduced significantly as compared to other methods listed in Table 3.
TABLE 3
Comparison of LIP with current RSA methods
Special Quadratic Sieve
General Quadratic
method
Trial division method
Method
Sieve Method
note
An exhaustive brute
A heuristic approach
A heuristic approach
force factorization.
neglect using decimal
neglect using decimal
Least efficient.
digits of α0, α1, . . . , αλ.
digits of α0, α1, . . . , αλ.
Running time depends
Running time
on the size of smallest
depends on the size of
prime factor. It may not
0.
converge to a feasible
It may not converge to
solution.
a feasible solution.
feature
Need to pre-know all
Need to fit properties of
Need to specify and
primes smaller than
prime factors works best
test hard smooth
√{square root over (θ)}.
when two prime factors
functions in the
are close.
solution process.
Usually being applied
before general quadratic
sieve methods to remove
small factors.
LIP Method provided by the present invention
note
An optimization approach, using decimal digits of α0, α1, . . . , αλ to form
equations, with solving by linear integer programs.
feature
No need to pre-know primes.
No need to specify extra parameters.
No need to fit properties of prime factors.
The system 100 can be applied to secure data transmissions in RSA encryption, such as public key encryption/decryption and digital signatures.
For public key encryption/decryption, during key generation, two large prime numbers are privately selected and multiplied together to create a semiprime number. This semiprime number becomes part of the public key, while the prime numbers are kept secret and contribute to the private key. The system 100 is utilized to generate these prime numbers. In the processes of encryption and decryption, the sender uses the recipient's public key to encrypt the message, and the recipient subsequently employs their private key to decrypt the message. If someone attempts to decrypt the message without the private key, they would need to factorize the semiprime number from the public key back into the original primes. This is a highly challenging and time-consuming computational problem, especially considering that the prime numbers used are typically very large. The system 100 can be used for determine the prime numbers for further determining the private key.
For digital signatures, the sender uses their private key to create a signature, and the recipient uses the sender's public key to verify it. The security of the signature relies on the difficulty of factorizing the semiprime number in the public key. The system 100 is employed to determine the private key for digital signatures.
In the present disclosure, spatial descriptions, such as “above,” “on,” “below,” “up,” “left,” “right,” “down,” “top,” “bottom,” “vertical,” “horizontal,” “side,” “upper,” “over,” “under,” and so forth, are specified with respect to a certain component or group of components, or a certain plane of a component or group of components, to orient the component(s) as shown in the associated figure. The spatial descriptions used herein are for illustrative purposes only, and practical implementations of the structures described herein can be spatially arranged in any orientation or manner.
As used herein and not otherwise defined, the terms “substantially,” “substantial,” “approximately” and “about” are used to describe and account for small variations. When used in conjunction with an event or circumstance, the terms can encompass instances in which the event or circumstance occurs precisely as well as instances in which the event or circumstance occurs to a close approximation. For example, when used in conjunction with a numerical value, the terms can encompass a range of variation of less than or equal to ±10% of that numerical value.
The foregoing description of the present invention has been provided for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations will be apparent to the practitioner skilled in the art.
The embodiments were chosen and described in order to best explain the principles of the invention and its practical application, thereby enabling others skilled in the art to understand the invention for various embodiments and with various modifications that are suited to the particular use contemplated.Inventors (2)
- Han-Lin LiHong Kong, HK
- Way KuoHong Kong, HK
Assignees (1)
- City University of Hong KongHong Kong, HK
CPC (2)
H04L9/302H04L9/3033
IPC (1)
H04L9/30
Backward citations (6)
US11456863[B1]US2020/0304306[A1]US2021/0344476[A1]US2022/0166618[A1]US2024/0235834[A1]US2025/0094524[A1]
Source: ipg260505.zip (2026-05-05)