Kernel Factor Pairs for Semiprime Factorization

Han-Lin Li¹, Shu-Cherng Fang², Way Kuo³, Nianrui Lin⁴

¹Department of Computer Science, City University of Hong Kong, Hong Kong, China.
²Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, USA.
³Hong Kong Institute for Advanced Study and Department of Data Science, City University of Hong Kong, Hong Kong, China.
⁴Department of Systems Engineering, City University of Hong Kong, Hong Kong, China.

DOI: 10.4236/apm.2025.159032                

Abstract

We show that any semiprime number can be factorized as the product of two prime numbers in the form of a kernel factor pair of two out of 48 root numbers. Specifically, each natural number without factors of 2, 3, 5 and 7 can be traced back to one unique number of a total of 48 root numbers falling in $\left[11,220\right]$ in periods of length 210. Unlike the commonly used sieve-based methods, under no preconditions, will the proposed kernel-factor-pair-based algorithm be guaranteed to successfully factorize any given semiprime $\alpha$ by searching over $1/2\log \alpha$ binary variables. The proposed method is well structured for factorization in breaking RSA encryption and is readily applicable for parallel computation.

Keywords

Semiprimes, Factorization, Factor-Pairs Table

1. Introduction

One of the greatest theorems of mathematics states that any natural number can be represented uniquely as a product of primes [1] [2]. Over years, prime numbers have been an important topic of number theory [3] [4]. Primes exhibit numerous interesting properties and are widely used in many fields in recent years, such as data science, cryptography , color theory [5] and reliability design .

Semiprime factorization methods are to decompose a semiprime number into its two prime factors, which serve as the key to cryptography including RSA public key encryption and RSA digital signature [6]-[12].

To the best of our knowledge, almost all available semiprime factorization methods are sieve-based, which can be classified into the following three categories [13] [14]:

• Category 1: The Trivial Sieve Method [15] comes from the well-known Aristotle sieve technique of utilizing exhaustive brute force to factorize a semiprime number. The Wheel Sieve Method [16] [17] identifies potential prime numbers starting from a small wheel and expanding to larger ones which improves the Trivial Sieve Method.

• Category 2: The Quadratic Sieve Method [18] includes the Pollard’s Rho [19] and Lenstra Elliptic Curve techniques [20]-[22].

• Category 3: The General Sieve Method [8] [23] includes the General Number Field Sieve (GNFS) and Schnorr methods [24]-[26].

Each of the above-mentioned sieve-based methods may suffer from the following limitations:

i) They often employ heuristic techniques to factorize a semiprime number, guaranteeing no convergence to a feasible solution. For example, the GNFS method depends on the specification of two polynomial functions [13] [23]. Similarly, since Pollard’s Rho method [19] is a probabilistic algorithm, it may not reach a convergent solution.

ii) Some require a good deal of pre-known information in the factorization process. For example, the Trivial Sieve method needs to know all prime numbers smaller than $\sqrt{\alpha }$ beforehand to factorize a semiprime number $\alpha$ , while the GNFS method likely uses more than half of its computing time to detect whether a number is smooth or not [13].

iii) Sieve methods often induce high space complexity. For example, to factorize a semiprime $\alpha$ , the Trivial Sieve method needs to reserve a large memory space to store $\sqrt{\alpha }$ pre-known primes for computations. The space complexity gets higher as $\alpha$ grows larger.

iv) Often needed by some of the methods are the special structure for a given semiprime. For example, the GNFS method can only factorize a semiprime with limited smoothness values [13]. Similarly, Pollard’s Rho [19] and Elliptic Curve [22] methods are special purpose algorithms, whose running time depends on the size of the smaller prime factor of a given semiprime number.

v) Wheel Sieve is an improvement of the method of Sieve of Eratosthenes. Such methods are intended to construct a prime list using the first few primes. Pritchard’s method [16], proposed in 1982, is one of the early works that explored the concept of wheels for factorization. The idea has been elaborated by others such as [17] into various forms. The wheel-sieve-based algorithms in general suffer from the difficulties of clearly identifying or distinguishing primes and composites. Consequently, the solutions usually get fuzzy when the involved numbers become large.

Recently, Li, Fang and Kuo discovered the Periodic Table of Primes (PTP) which reveals all primes and composites with no factors of 2, 3, 5 and 7 exclusively in a compact table. One unique feature of the PTP is to identify the cyclic appearance of composites through the Cyclic Table of Composites (CTC) , and then differentiate primes and composites from a feasible set like that used in the wheel sieve, but subject to no preconditions. The PTP clearly shows that the ratio of the number of primes to that of the composites approaches zero when the table size grows. An early version of the SSRN archive [28] also provided examples to highlight the potential of using the PTP for factorization.

To overcome the general difficulties and limitations of sieve-based factoring methods, we now propose an innovative scheme for semiprime factorization. By extending our previous work of building the PTP [27], we introduce the concepts of “factor pairs” and “kernel factor pairs” for fast factorization. A short table of all factor pairs listed in 48 rows and 28 columns is constructed to steer the factorization of any given semiprime under no preconditions. With the Factor-Pairs Table (Table 1) in hand, there is no need to know, calculate, and store any primes that come before $\sqrt{\alpha }$ for a given semiprime $\alpha$ . This may significantly reduce the space complexity issue faced by some sieve-based methods. The number of potential factor pairs involved in selecting a kernel factor pair corresponding to a given semiprime $\alpha$ naturally leads to the design of a highly parallelable algorithm for semiprime factorization.

The proposed method is well structured for semiprimes factorization when breaking RSA encryption and readily applicable for parallel computation.

The rest of the paper is organized as follows. In Section 2, we introduce the basic theory of semiprime factorization based on the concepts of factor pair and kernel factor pair. In Section 3, we provide a framework of designing a Linear-search Factor-pair Kernel (LFK) algorithm for semiprime factorization. The proposed LFK algorithm is presented in Section 4 while a complexity analysis is given in Section 5. An illustrative example is provided in Section 6. The paper ends with conclusions and discussions in Section 7.

The following notations are used throughout the paper:

• $\alpha$ : a semiprime number

• $N_0=\left\{0,1,2,\cdots \right\}$ : all non-negative integers

• $N=\left\{1,2,3,\cdots \right\}$ : all natural numbers

• $\Lambda$ = {$n\in N|n>1$ and $n$ has no factors of 2, 3, 5 and 7}

• $P$ = {$n\in N|n>1$ and $n$ is a prime}: all prime numbers

• $P_S$ = {$n\in N|n$ is a product of two primes}: all semiprime numbers

• ${\left[a,b\right]}_N=\left\{n\in N|a\le n\le b\right\}$

• ${\text{FT}}_{210}$ = a table of 48 rows and 28 columns consisting of all factor-pairs

• $\lceil x\rceil$ = ceiling function of the smallest integer greater than or equal to $x$

• $\lfloor x\rfloor$ = floor function of the largest integer smaller than or equal to $x$

2. Basic Theory

For a given number $n\in N$ , it is relatively easy to identify if it has any factor of 2, 3, 5 and 7. Since $2\times 3\times 5\times 7=210$ , we may group every 210 numbers in one period starting from 11, i.e., ${\left[11,220\right]}_N$ , ${\left[221,430\right]}_N$ , ${\left[431,640\right]}_N$ , … Checking the numbers in ${\left[11,220\right]}_N$ , we can identify 48 numbers which have no factors of 2, 3, 5 and 7, i.e., ${\left[11,220\right]}_N\cap \Lambda =48$ . These 48 numbers are listed as the roots (root numbers) in the following set:

$\begin{array}{l}S=\{r_1=11,r_2=13,r_3=17,r_4=19,r_5=23,r_6=29,r_7=31,r_8=37,r_9=41,\\ r_{10}=43,r_{11}=47,r_{12}=53,r_{13}=59,r_{14}=61,r_{15}=67,r_{16}=71,r_{17}=73,\\ r_{18}=79,r_{19}=83,r_{20}=89,r_{21}=97,r_{22}=101,r_{23}=103,r_{24}=107,\\ r_{25}=109,r_{26}=113,r_{27}=121,r_{28}=127,r_{29}=131,r_{30}=137,r_{31}=139,\\ r_{32}=143,r_{33}=149,r_{34}=151,r_{35}=157,r_{36}=163,r_{37}=167,r_{38}=169,\\ r_{39}=173,r_{40}=179,r_{41}=181,r_{42}=187,r_{43}=191,r_{44}=193,r_{45}=197,\\ r_{46}=199,r_{47}=209,r_{48}=211\}.\end{array}$

A quick observation shows that 5 roots in S are composite numbers, namely, $r_{27}=121=11\times 11$ , $r_{32}=143=11\times 13$ , $r_{38}=169=13\times 13$ , $r_{42}=187=11\times 17$ and $r_{47}=209=11\times 19$ , and the rest 43 root numbers in S are primes.

An immediate result shows that any natural number $\alpha$ without factors of 2, 3, 5 and 7, no matter it is a prime or composite number, can be traced back to a unique root $r_i\in S$ .

Theorem 1.

A number $\alpha \in \Lambda$ if and only if there exists a unique $r_i\in S$ and $k\in N_0$ such that $\alpha =r_i+210\times k$ .

Proof.

i) If $\alpha =r_i+210\times k$ for any $r_i\in S$ and $k\in N_0$ , then $\alpha \in \Lambda$ because $r_i$ is the residue of $\alpha$ divided by 2, 3, 5 and 7.

ii) If $\alpha \in \Lambda$ , then we let $k=\lfloor \left(\alpha -10\right)/210\rfloor \in N_0$ and $\alpha -210\times k\in {\left[11,220\right]}_N\cap \Lambda$ . Hence there exists a unique $r_i\in S$ such that $\alpha =r_i+210\times k$ . ◻

Theorem 1 ensures that every number $\alpha$ without factors of 2, 3, 5 and 7 is an offspring of one unique root $r_i\in S$ in the $k$ -th period of 210. Here we emphasize that any prime number greater than 10 is rooted back to a unique $r_i\in S$ . Moreover, we enlist all numbers without factors of 2, 3, 5 and 7 as below:

Period $k=0$ , ${\left[11,220\right]}_N\cap \Lambda =\left\{q_1=r_1,q_2=r_2,\cdots ,q_{48}=r_{48}\right\}$ .

Period $k=1$ , ${\left[221,430\right]}_N\cap \Lambda =\left\{q_1+210,q_2+210,\cdots ,q_{48}+210\right\}$ ,

$⋮$

Period $k=\overline{k}$ , ${\left[11+210\overline{k},220+210\overline{k}\right]}_N\cap \Lambda =\{q_1+210\times \overline{k},q_2+210\times \overline{k},\cdots ,q_{48}+$$210\times \overline{k}\}$ .

We now focus on semiprime numbers. Since any semiprime $\alpha \in P_S$ is a product of two primes and it is easy to identify if $\alpha$ has any factor of 2, 3, 5 or 7, without loss of generality, we may limit our consideration to $\alpha \in P_S\cap \Lambda$ . In this case, from Theorem 1, there exists a unique $r_i\in S$ , $k_i\in N_0$ such that

$\alpha =r_i+210k_i$ . (1)

Moreover, there must exist $r_j$ , $r_{\widehat{j}}\in S$ and $k_j$ , $k_{\widehat{j}}\in N_0$ such that

$\alpha =\left(r_j+210k_j\right)\times \left(r_{\widehat{j}}+210k_{\widehat{j}}\right)$ . (2)

Note that $r_j=r_{\widehat{j}}$ and/or $k_j=k_{\widehat{j}}$ are allowed.

Equation (1) and Equation (2) require that

$\frac{r_j\times r_{\widehat{j}}-r_i}{210}=k_i-\left(k_j\times r_{\widehat{j}}+k_{\widehat{j}}\times r_j+210k_j\times k_{\widehat{j}}\right).$

Therefore, $r_j\times r_{\widehat{j}}-r_i$ has to be a multiple of 210. We call $\left(r_j,r_{\widehat{j}}\right)\in S\times S$ a factor pair with respect to $r_i\in S$ and denote the pair by $\left(q_{j|i},q_{\widehat{j}|i}\right)$ where $q_{j|i}=r_j$ and $q_{\widehat{j}|i}=r_{\widehat{j}}$ . When $r_j=r_{\widehat{j}}$ , we call $\left(q_{j|i}=r_j,q_{\widehat{j}|i}=r_{\widehat{j}}\right)$ a co-factor pair with respect to $r_i$ .

Obtained through some elaborative calculations, the Factor-Pairs Table ${\text{FT}}_{210}$ (Table 1) shows all factor/co-factor pairs $\left(q_{j|i},q_{\widehat{j}|i}\right)\in S\times S$ with respect to each $r_i\in S$ in the arrangement of $q_{j|i}\le q_{\widehat{j}|i}$ . For each $r_i\in S$ , $i=1,2,\cdots ,48$ , we define $Q\left(i\right)=\left\{\left(q_{j|i},q_{\widehat{j}|i}\right)\in S\times S|q_{j|i}\le q_{\widehat{j}|i}\text{and}{q}_{j|i}\times q_{\widehat{j}|i}-r_i\text{is}\text{a}\text{multiple}\text{of}210\right\}$.

From ${\text{FT}}_{210}$ , we see that (i) for $i=18,25,27,34,38$ and 48, $\left|Q\left(i\right)\right|=28$ with 4 co-factor pairs, (ii) for the rest 42 $r_i$ ’s, $\left|Q\left(i\right)\right|=24$ with no co-factor pairs, and (iii) $q_{j|i}\times q_{\widehat{j}|i}\ge r_i$ for all $r_i\in S$ .

Summarizing the above, we reach the next result.

Theorem 2.

For any given semiprime $\alpha$ with no factors of 2, 3, 5 and 7, i.e., $\alpha \in P_S\cap \Lambda$ , there exists a unique $r_i\in S$ with $k_i\in N_0$ and a factor pair $\left(q_{j|i},q_{\widehat{j}|i}\right)\in Q\left(i\right)$ with $k_j$ , $k_{\widehat{j}}\in N_0$ such that

$\alpha =r_i+210k_i=\left(q_{j|i}+210k_j\right)\times \left(q_{\widehat{j}|i}+210k_{\widehat{j}}\right)$ . (3)

It is important to note that since the factorization of a semiprime $\alpha$ is unique, the corresponding factor pair of $\alpha$ , i.e., $\left(q_{j|i},q_{\widehat{j}|i}\right)\in Q\left(i\right)$, is unique. We call it the kernel factor pair associated with the semiprime $\alpha$ .

3. Algorithm Design

Based on Theorem 2, we introduce the overall design of an algorithm for semiprime factorization based on the kernel factor pair.

For a given semiprime $\alpha$ , it is easy to check if $\alpha$ has a factor of 2, 3, 5 or 7. Without loss of generality, we may assume that $\alpha \in P_S\cap \Lambda$ . The root number $r_i\in S$ can be readily identified by computing

$r_i=\alpha -\lfloor \frac{\alpha -10}{210}\rfloor \times 210$ (4)

with

$k_i=\lfloor \frac{\alpha -10}{210}\rfloor .$

Once $r_i$ is determined for $i\in \left\{1,\cdots ,48\right\}$ , then we check each factor pair $\left(q_{j|i},q_{\widehat{j}|i}\right)\in Q\left(i\right)$ to see if Equation (3) is satisfied by certain $k_j$ , $k_{\widehat{j}}\in N_0$ . If the answer is Yes, then $(q_{j|i},q_{\widehat{j}|i})$ is a kernel factor pair for factoring $\alpha$ , and the existence and uniqueness of a kernel factor pair in $Q\left(i\right)$ for $\alpha \equiv r_i\left(\mathrm{mod}210\right)$ is assured by Theorem 2.

For a given factor pair $\left(q_{j|i},q_{\widehat{j}|i}\right)\in Q\left(i\right)$, to check if it is a kernel factor pair for $\alpha$ is equivalent to finding $\theta$ and $\widehat{\theta }\in N_0$ such that

$\alpha =\left(q_{j|i}+210\times \theta \right)\left(q_{\widehat{j}|i}+210\times \widehat{\theta }\right),$

or equivalently,

$\frac{\alpha -q_{j|i}\times q_{\widehat{j}|i}}{210}=q_{j|i}\times \widehat{\theta }+q_{\widehat{j}|i}\times \theta +210\times \theta \times \widehat{\theta }.$

Denoting

${\sigma }_{j|i}=\frac{\alpha -\left(q_{j|i}\times q_{\widehat{j}|i}\right)}{210}\left(\le \frac{\alpha -{11}^2}{210}\right),$ (5)

we have

${\sigma }_{j|i}=q_{j|i}\times \widehat{\theta }+q_{\widehat{j}|i}\times \theta +210\times \theta \times \widehat{\theta }.$ (6)

Consequently, we may perform a less desirable “quadratic search” on $\theta ,\widehat{\theta }\in \left\{0,1,\cdots ,\lceil {\sigma }_{j|i}/11\rceil \right\}$ simultaneously to see if $\left(q_{j|i},q_{\widehat{j}|i}\right)$ is a kernel factor pair for $\alpha$ .

4. LFK—A Linear Search Algorithm

To reduce the complexity involved in the quadratic search, we conduct further analysis to reach a “linear search” algorithm. The algorithm presented here is closely related to the theoretical framework developed in [29], which involves an innovative algorithm for general primality testing. In this paper, matching the concept of “factor pairs” with the characteristics of “semiprime”, we focus on developing an elaborated algorithm specifically for semiprime factorization.

Without loss of generality, we assume that $\theta \ge \widehat{\theta }\ge 0$ in Equation (6) which leads to

${\sigma }_{j|i}\ge 210\times \theta \times \widehat{\theta }\ge 210{\widehat{\theta }}^2.$

Together with Equation (5), we have

${\widehat{\theta }}^2\le \frac{{\sigma }_{j|i}}{210}\le \frac{\alpha -{11}^2}{{210}^2}.$

Hence $\widehat{\theta }\le \sqrt{\alpha }/210$ . This means that it is sufficient to check for $\widehat{\theta }\in \left\{0,1,\cdots ,\lceil \sqrt{\alpha }/210\rceil \right\}$.

Once $\widehat{\theta }$ is selected, Equation (6) indicates that

$\theta =\frac{{\sigma }_{j|i}-q_{j|i}\times \widehat{\theta }}{q_{\widehat{j}|i}+210\widehat{\theta }}$ (7)

should be an integer greater than or equal to $\widehat{\theta }$ .

Our approach leads to the following LFK method for semiprime factorization.

Step1: Input a semiprime number $\alpha$ . If $\alpha$ can be fully divided by 2, 3, 5 or 7, then stop with a simple factorization.

Step2: Determine the root number $r_i\in S$ .

• Set $r_i=\alpha -\lfloor \frac{\alpha -10}{210}\rfloor \times 210$ .

Step3: Determine the kernel factor pair in $Q\left(i\right)$ .

• Pick one unchecked factor pair a time in $Q\left(i\right)$ from ${\text{FT}}_{210}$ , say $\left(q_{j|i},q_{\widehat{j}|i}\right)$.

• Set ${\sigma }_{j|i}=\left(\alpha -q_{j|i}\times q_{\widehat{j}|i}\right)/210$ .

Step4: Check for possible $\theta \ge \widehat{\theta }\ge 0$ .

• For $\widehat{\theta }\in \left\{0,1,\cdots ,\lceil \sqrt{\alpha }/210\rceil \right\}$, compute $\theta$ using Equation (7).

• If $\theta$ is an integer and $\theta \ge \widehat{\theta }$ , then output $\left(q_{j|i},q_{\widehat{j}|i}\right)$ as the kernel factor pair and $\alpha =\left(q_{j|i}+210\times \theta \right)\times \left(q_{\widehat{j}|i}+210\times \widehat{\theta }\right)$ . Stop the algorithm.

Step5: Check for possible $0\le \theta \le \widehat{\theta }$ .

• For $\theta \in \left\{0,1,\cdots ,\lceil \sqrt{\alpha }/210\rceil \right\}$ , compute

$\widehat{\theta }=\frac{{\sigma }_{j|i}-q_{\widehat{j}|i}\times \theta }{q_{j|i}+210\theta }.$

• If $\widehat{\theta }$ is an integer and $\widehat{\theta }>\theta$ , then output $\left(q_{j|i},q_{\widehat{j}|i}\right)$ as the kernel factor pair and $\alpha =\left(q_{j|i}+210\times \theta \right)\times \left(q_{\widehat{j}|i}+210\times \widehat{\theta }\right)$ . Stop the algorithm.

Step6: Mark the current factor pair as “checked” and Return to Step 3 for the next unchecked factor pair in $Q\left(i\right)$ .

As a direct consequence of Theorem 2, we obtain the next result.

Corollary 3.

The proposed LFK algorithm always terminates in finite steps with a unique kernel factor pair for any given semiprime $\alpha$ .

5. Complexity Analysis

For any given semiprime number $\alpha \in P_S$ , we know $\alpha =p_1\times p_2$ for a unique pair of $p_1\in P$ and $p_2\in P$ . Except that $p_1$ or $p_2$ is 2, 3, 5 or 7, which can be easily verified, $\alpha$ has no factors of 2, 3, 5 and 7, i.e., $\alpha \in P_S\cap \Lambda$ . Theorem 1 assures that $\alpha$ has a unique root number $r_i\in S$ . Table ${\text{FT}}_{210}$ shows that there are either 24 or 28 factor pairs in $Q\left(i\right)$ for a semiprime rooted at $r_i$ .

Theorem 2 further confirms the existence of a unique kernel factor pair $\left(q_{j|i},q_{\widehat{j}|i}\right)\in Q\left(i\right)$ such that $\alpha$ can be factorized as the product of $\left(q_{j|i}+210\times \theta \right)$ and $\left(q_{\widehat{j}|i}+210\times \widehat{\theta }\right)$ .

Steps 1 - 3 of the LFK Algorithm set up the platform with simple calculations. Considering the possible relations between $\theta$ and $\widehat{\theta }$ , the desired kernel factor pair can be identified by searching through $1+\lceil \sqrt{\alpha }/210\rceil$ integer values for $\widehat{\theta }$ first and then, when needed, searching through $1+\lceil \sqrt{\alpha }/210\rceil$ integer values for $\theta$ . Therefore, the LFK algorithm involves at most $28\times 2=56$ linear searches over $1+\lceil \sqrt{\alpha }/210\rceil$ integer values. In other words, a rough estimation of the required work for factoring a semiprime $\alpha$ involves no more than searching through $56\times \sqrt{\alpha }/210\approx \sqrt{\alpha }/4$ integer values. The previous analysis leads to the next result.

Theorem 4.

The LFK algorithm requires at most 56 linear searches over the integer values in $\left[0,\lceil \sqrt{\alpha }/210\rceil \right]$ to find a unique kernel factor pair for any given semiprime $\alpha$ .

It is worthy to point out that the tasks for searching the kernel factor pair out of the 28 (or 24) factor pairs in $Q\left(i\right)$ can be conducted independently in parallel.

6. Illustrating Example

We illustrate the LFK algorithm using the following example to factor an 11-digit semiprime $\alpha =12648677849$ .

Step1: Since $\alpha$ cannot be fully divided by 2, 3, 5 and 7, we know $\alpha \in P_S\cap \Lambda$ .

Step2: Since $\alpha =59+210\times 60231799$ , $r_{13}=59$ is the root number of $\alpha$ .

Step3: We sequentially check the 24 factor-pairs in $Q\left(13\right)$ from ${\text{FT}}_{210}$ , namely, $Q\left(13\right)=\left\{\left(11,139\right),\left(13,53\right),\left(17,127\right),\cdots ,\left(71,199\right),\cdots ,\left(179,181\right)\right\}$ . After taking 12 iterations going through Steps 4 and 5 to check $\left(q_{j|13},q_{\widehat{j}|13}\right)$ for $j=1,2,\cdots ,12$ without finding any feasible solution, we check $\left(q_{13|13},q_{\widehat{13}|13}\right)=\left(71,199\right)$. Calculate ${\sigma }_{13|13}=\frac{\alpha -71\times 199}{210}=60231732$ .

Step4: Check for possible $\theta \ge \widehat{\theta }\ge 0$ .

• Compute

• $\theta =\frac{{\sigma }_{j|i}-q_{j|i}\times \widehat{\theta }}{q_{\widehat{j}|i}+210\widehat{\theta }}=\frac{60231732-71\widehat{\theta }}{199+210\widehat{\theta }}$

• for each $\widehat{\theta }\in \left\{0,1,\cdots ,\lceil \sqrt{\alpha }/210\rceil \right\}=\left\{0,1,\cdots ,536\right\}$. Since none of the $\widehat{\theta }$ ’s are integers, continue to Step 5.

Step5: Check for possible $0\le \theta \le \widehat{\theta }$ .

• Compute $\widehat{\theta }=\frac{{\sigma }_{j|i}-q_{\widehat{j}|i}\times \theta }{q_{j|i}+210\theta }=\frac{60231732-199\theta }{71+210\theta }$ for each $\theta \in \left\{0,1,\cdots ,536\right\}$ . When $\theta =473$ , $\widehat{\theta }=\frac{60231732-199\times 473}{71+210\times 473}=605>\theta$ is an integer. Output (71, 199) as the kernel factor pair and $\alpha =12648677849=\left(71+210\times 473\right)\times \left(199+210\times 605\right)=99401\times 127249$ .

7. Conclusions and Discussions

In this paper, we introduce the concepts of factor pairs and kernel factor pairs to form a new framework for designing an efficient semiprime factoring algorithm that serves as the key input to the RSA algorithm for computer encryption. Unlike commonly developed sieve-based methods, the proposed kernel-factor-pair-based LFK algorithm is proven to successfully factorize any given semiprime $\alpha$ by taking at most 56 linear searches over the integer values in [0, $\lceil \sqrt{\alpha }/210\rceil$ ]. The overall computational complexity is less than searching through $\lceil \sqrt{\alpha }/4\rceil$ integer values with simple calculations. The LFK algorithm works under no preconditions and finds the exact factors for any given semiprime. The required search can be conducted naturally in parallel for fast computations.

As pointed out in [27], instead of eliminating the factors of 2, 3, 5 and 7 for consideration, an “extended” PTP table can be easily built by eliminating fewer factors, such as 2, 3, 5 only, or by eliminating more factors, such as 2, 3, 5, 7 and 11. Since the construction of the PTP is not sieve-based, it requires no prior knowledge or processing efforts of any other primes. In fact, an extended PTP that eliminates more factors for consideration will have a longer period but with more roots. The concepts of factor pairs and kernel factor pair follow accordingly for the LFK algorithm to prevail.

Some further discussions are as follows:

1) Notice that the LFK searches $\theta$ (and $\widehat{\theta }$ ) through the integer values from 0 to $\lceil \sqrt{\alpha }/210\rceil$ . When $\alpha \approx 2^d$ becomes a huge number in $d$ digits, the searching range could be a concern. In this case, by adopting a prime-logarithmic technique in [4], we can simply find an integer $m$ such that $2^m\ge \lceil \sqrt{\alpha }/210\rceil \ge 2^{m-1}$ and introduce $m$ ($~\frac{1}{2}\log \alpha$ ) 0 - 1 binary variables $u_1,\cdots ,u_m$ such that $\theta$ can be represented by

$\theta =2^0{u}_1+2^1{u}_2+2^2{u}_3+\cdots +2^{m-1}{u}_m$ for $u_i\in \left\{0,1\right\}$ .

In other words, the task of searching $\theta$ through the integer values from 0 to $\lceil \sqrt{\alpha }/210\rceil$ can be replaced by checking the values of $m$ (about $1/2\log \alpha$ ) binary variables. For instance, to factorize a semiprime $\alpha =2^{32}+1=4294967297$ , we only need 16 binary variables to find the solution being

$2^{32}+1=\left(11+210\times 3\right)\times \left(157+210\times 31906\right)=641\times 6700417.$

However, the performance of the prime-logarithmic technique developed by Li et al. [4] strongly depends on, firstly, the way of formulating the related linear binary programming problem, and secondly, the software package used to solve the linear binary programming problem. This will remain for further study.

2) Compared with the commonly used sieve-based semiprime factoring methods, we observe that:

(1) Heuristic versus deterministic: Many sieve-based methods are heuristic and may not converge to a feasible solution. However, the proposed LFK algorithm is a deterministic approach which guarantees to factorize any semiprime number into two prime factors.

(2) High space complexity versus low space complexity: The Trial Sieve Method requires a high space complexity to store all primes that come before $\sqrt{\alpha }$ , while, with the ${\text{FT}}_{210}$ in hand, the LFK algorithm needs at most 28 memory spaces to store the corresponding factor pairs.

(3) Hard-to-manage versus manageable parallel computing: Sieve-based methods may generate numerous subproblems which are hard to arrange for parallel processing. The LFK algorithm can easily arrange all subproblems into 24 or 28 processes to be computed parallelly.

In conclusion, fast semiprime factorization is essential for breaking RSA encryption. The kernel-factor-based LFK algorithm provides a new angle for further investigation on designing efficient factoring methods for information security.

Acknowledgements

We thank Professor Xiaohua Jia of City University of Hong Kong and an anonymous reviewer for reviewing and providing valuable comments to the article. We are grateful for the in-kind-support from NTU and the financial support for Way Kuo from the Hong Kong Institute for Advanced Study (CityU 9610556).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Zagier, D. (1977) The First 50 Million Prime Numbers. The Mathematical Intelligencer, 1, 7-19. https://doi.org/10.1007/bf03351556
[2]	Zagier, D. (1997) Newman’s Short Proof of the Prime Number Theorem. The American Mathematical Monthly, 104, 705-708. https://doi.org/10.1080/00029890.1997.11990704
[3]	Dickson, L.E. (2005) History of the Theory of Numbers, Volume II: Diophantine Analysis. Dover Publications.
[4]	Li, H., Huang, Y., Fang, S. and Kuo, W. (2021) A Prime-Logarithmic Method for Optimal Reliability Design. IEEE Transactions on Reliability, 70, 146-162. https://doi.org/10.1109/tr.2020.3020597
[5]	Li, H., Fang, S., Lin, B.M.T. and Kuo, W. (2023) Unifying Colors by Primes. Light: Science & Applications, 12, Article No. 32. https://doi.org/10.1038/s41377-023-01073-x
[6]	Konheim, A.G. (2006) Computer Security and Cryptography. Wiley. https://doi.org/10.1002/0470083980
[7]	Li, D., Luo, M., Zhao, B. and Che, X. (2018) Provably Secure APK Redevelopment Authorization Scheme in the Standard Model. Computers, Materials & Continua, 56, 447-465. https://doi.org/10.3970/cmc.2018.03692
[8]	RSA Laboratories (2013) The RSA Factoring Challenge. https://web.archive.org/web/20130921043459/ http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge.htm
[9]	Shor, P.W. (1997) Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26, 1484-1509. https://doi.org/10.1137/s0097539795293172
[10]	Shoshina, A.V., Borzunov, G.I. and Ivanova, E.Y. (2021) Application of Bio-Inspired Algorithms to the Cryptanalysis of Asymmetric Ciphers on the Basis of Composite Number. 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus), St. Petersburg, 26-29 January 2021, 2399-2403. https://doi.org/10.1109/elconrus51938.2021.9396242
[11]	Upadhyay, S. and Gupta, V.K. (2022) A Literature Review on the Concept of Cryptography and RSA Algorithm. International J of Advance and Innovative Research, 9, 237-240.
[12]	Vandersypen, L.M.K., Steffen, M., Breyta, G., Yannoni, C.S., Sherwood, M.H. and Chuang, I.L. (2001) Experimental Realization of Shor’s Quantum Factoring Algorithm Using Nuclear Magnetic Resonance. Nature, 414, 883-887. https://doi.org/10.1038/414883a
[13]	Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thome, E. and Zimmermann, P. (2022) The State of the Art in Integer Factoring and Breaking Public-Key Cryptography. IEEE Security & Privacy, 20, 80-86. https://doi.org/10.1109/msec.2022.3141918
[14]	Zhang, X., Li, M., Jiang, Y. and Sun, Y. (2019) A Review of the Factorization Problem of Large Integers. In: Sun, X., Pan, Z. and Bertino, E., Eds., Artificial Intelligence and Security, Springer, 202-213. https://doi.org/10.1007/978-3-030-24268-8_19
[15]	Pomerance, C. and Erdös, P. (1996) A Tale of Two Sieves. Notices of the American Mathematical Society, 43, 1473-1485.
[16]	Pritchard, P. (1982) Explaining the Wheel Sieve. Acta Informatica, 17, 477-485. https://doi.org/10.1007/bf00264164
[17]	Wikipedia Contributors (2025) Wheel Factorization. https://en.wikipedia.org/w/index.php?title=Wheel_factorization&oldid=1279299441
[18]	Atkin, A.O.L. and Bernstein, D.J. (2003) Prime Sieves Using Binary Quadratic Forms. Mathematics of Computation, 73, 1023-1030. https://doi.org/10.1090/s0025-5718-03-01501-1
[19]	Pollard, J.M. (1993) The Lattice Sieve. In: Lenstra, A.K. and Lenstra, H.W., Eds., The Development of the Number Field Sieve, Springer, 43-49. https://doi.org/10.1007/bfb0091538
[20]	Dixon, B. and Lenstra, A.K. (1994) Factoring Integers Using SIMD Sieves. In: Helleseth, T., Ed., Advances in Cryptology—EUROCRYPT’93. EUROCRYPT 1993, Springer, 28-39.
[21]	Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thomé, E., Bos, J.W., et al. (2010) Factorization of a 768-Bit RSA Modulus. In: Rabin, T., Ed., Advances in Cryptology—CRYPTO 2010, Springer, 333-350. https://doi.org/10.1007/978-3-642-14623-7_18
[22]	Menezes, A. and Vanstone, S.A. (1993) Elliptic Curve Cryptosystems and Their Implementation. Journal of Cryptology, 6, 209-224.
[23]	Bai, S., Gaudry, P., Kruppa, A., Thomé, E. and Zimmermann, P. (2016) Factorisation of RSA-220 with CADO-NFS. https://inria.hal.science/hal-01315738
[24]	Schnorr, C.P. (2013) Factoring Integers by CVP Algorithms. In: Fischlin, M. and Katzenbeisser, S., Eds., Number Theory and Cryptography, Springer, 73-93. https://doi.org/10.1007/978-3-642-42001-6_6
[25]	Schnorr, C.P. (2021) Fast Factoring Integers by SVP Algorithms. https://eprint.iacr.org/2021/933
[26]	Tang, X., Xu, J. and Duan, B. (2018) A Memory-Efficient Simulation Method of Grover’s Search Algorithm. Computers, Materials & Continua, 57, 307-319. https://doi.org/10.32604/cmc.2018.03693
[27]	Li, H., Fang, S. and Kuo, W. (2024) The Periodic Table of Primes. Advances in Pure Mathematics, 14, 394-419. https://doi.org/10.4236/apm.2024.145023
[28]	Li, H., Fang, S. and Kuo, W. (2024) The Periodic Table of Primes. SSRN Electronic Journal. https://doi.org/10.2139/ssrn.4742238
[29]	Li, H., Fang, S., Kuo, W. and Lin, N. (2025) Listing Prime Numbers Periodically. Advances in Pure Mathematics, 15, 247-268. https://doi.org/10.4236/apm.2025.154012