ABSTRACT

In accordance with the distributive traits of semiprimes’ divisors, the article proposes an approach that can find out the small divisor of a semiprime by parallel computing. The approach incorporates a deterministic search with a probabilistic search, requires less memory and can be implemented on ordinary multicore computers. Experiments show that certain semiprimes of 27 to 46 decimal-bits can be validly factorized with the approach on personal computer in expected time.

Keywords:

Parallel, Probabilistic, Integer Factorization, Semiprime

1. Introduction

A semiprime is an odd composite number N that has exactly two distinct prime divisors, say p and q, such that $3\le p<q$ . Factorization of the semiprimes has been a difficult problem in mathematics and computer science, especially factorization of a RSA number that is a large semiprime, as introduced and overviewed in articles [1] [2] [3] [4] [5] . Let $k=q/p$ be the divisor-ratio of the semiprime $N=pq$ ; article [6] discovered the genetic property of the odd integers and proved that the small divisor p can be calculated by finding the greatest common divisor (GCD) with an odd integer that lies in an odd interval $I_0$ that is determined by N itself; article [7] further pointed out that, by taking k to be a variable quantity, algorithms could be designed to factorize big semiprimes by parallel computing and the article also demonstrated a deterministic approach to factor the RSA numbers; article [8] recently made a further investigation on k’s influence to the distribution of p, showing that the interval $I_0$ is a cover of finite subintervals each of which is determined by a k and every two adjacent ones of which are linked with their unique common end. This means that p can be surely found out with a k-subdivision approach. Following such an idea, this paper makes an investigation on the new algorithm design for searching the odd integer that has GCD with N. As a result, an algorithm that incorporates a deterministic search with a probabilistic search is designed. This paper presents the related consequences. Section 2 lists the preliminaries for the later sections; Section 3 proves the mathematical foundations for the new algorithm; Section 4 introduces the new algorithm as well as its designing strategy and numerical experiments.

2. Preliminaries

This section lists the preliminaries that include definitions, symbols and lemmas, which are necessary for later sections.

2.1. Symbols and Notations

In this whole article, a semiprime $N=pq$ means p and q are both odd prime numbers and $3\le p<q$ . An odd interval $\left[a\mathrm{,}b\right]$ is a set of consecutive odd numbers that take a as the lower bound and b as the upper bound; for example, $\left[3,11\right]=\left\{3,5,7,9,11\right\}$ . Symbol $\lfloor x\rfloor$ is the floor function, an integer function of real number x that satisfies $\lfloor x\rfloor \le x<\lfloor x\rfloor +1$ ; symbol GCD means the greatest common divisor; let $m>0$ ; then $e_m^b$ , $e_m^p$ , $e_m^q$ and $e_m^0$ are defined by

$e_m^b=N_{\left(m+1,2^{m-1}-1\right)}=2^{m}N-1$

$e_m^p=2^{m}N-p$

$e_m^q=2^{m}N-q$

$e_m^0=e_m^b-2\left(\lfloor \frac{\sqrt{N}+1}{2}\rfloor -1\right)$

Symbol $A\Delta =\frac{B}{2}$ , which was defined in [8] , means A is half of B.

2.2. Lemmas

Lemma 1. (See in [8] ) Suppose $N=pq$ is an odd composite number and $k=\lfloor \frac{q}{p}\rfloor \ge 1$ ; then $e_m^p\in \left[e_m^{kl}\mathrm{,}{e}_m^{kr}\right]$ , where $m=\lfloor {\log }_{2}N\rfloor -1$ , $e_m^{kl}=e_m^b-2\left(\lfloor \frac{1}{2}\left(1+\sqrt{\frac{N}{k}}\right)\rfloor -1\right)$ , $e_m^{kr}=e_m^b-2\lfloor \frac{1}{2}\left(1+\sqrt{\frac{N}{k+1}}\right)\rfloor$ and $e_m^b=2^{m}N-1$.

Lemma 2. (See in [8] ) Suppose $N>1$ is an odd integer and $k_1<k_2$ are positive integers. Let $l{s}_{k_1}=\lfloor \frac{1}{2}\left(1+\sqrt{\frac{N}{k_1+1}}\right)\rfloor +1$ , $l{s}_{k_2}=\lfloor \frac{1}{2}\left(1+\sqrt{\frac{N}{k_2+1}}\right)\rfloor +1$ , $l{b}_{k_1}=\lfloor \frac{1}{2}\left(1+\sqrt{\frac{N}{k_1}}\right)\rfloor$ and $l{b}_{k_2}=\lfloor \frac{1}{2}\left(1+\sqrt{\frac{N}{k_2}}\right)\rfloor$ ; then it holds

$e_m^{k{l}_1}<e_m^{k{r}_1}\le e_m^{k{l}_2}<e_m^{k{r}_2}$

where $e_m^{k{l}_1}=e_m^b-2\left(l{b}_{k_1}-1\right)$ , $e_m^{k{l}_2}=e_m^b-2\left(l{b}_{k_2}-1\right)$ , $e_m^{k{r}_1}=e_m^b-2\left(l{s}_{k_1}-1\right)$ and $e_m^{k{r}_2}=e_m^b-2\left(l{s}_{k_2}-1\right)$.

Particularly, when $k_2=k_1+1$ it holds

$e_m^{k{l}_1}<e_m^{k{r}_1}=e_m^{k{l}_2}<e_m^{k{r}_2}$

Lemma 3. (See in [8] ) For arbitrary odd number $N>1$ , let $l{s}_i=\lfloor \frac{1}{2}\left(1+\sqrt{\frac{N}{i+1}}\right)\rfloor +1$ , $l{b}_i=\lfloor \frac{1}{2}\left(1+\sqrt{\frac{N}{i}}\right)\rfloor$ , $e_m^{il}=e_m^b-2\left(l{b}_i-1\right)$ and $e_m^{ir}=e_m^b-2\left(l{s}_i-1\right)$ , where $i=1,2,\cdots ,\omega$ are positive integers; then odd intervals $I_i=\left[e_m^{il},e_m^{ir}\right]$ satisfy

1) $I_i\cap I_{i+1}=e_m^{ir}$ ;

2) ${\displaystyle \underset{i=1}{\overset{i=\omega }{\cup }}{I}_i}=\left[e_m^0,e_m^{\omega r}\right]$ ;

3) ${\displaystyle \underset{i=1}{\overset{i=\infty }{\cup }}{I}_i}=\left[e_m^0,e_m^b\right]$ ; as illustrated in Figure 1.

Lemma 4. (See in [8] ) Let ${\Delta }_0=\lfloor \frac{\sqrt{N}+1}{2}\rfloor$ be the length of the odd interval $I_0=\left[e_m^0,e_m^b\right]$ , ${\Delta }_i$ and ${\Delta }_{i+1}$ be respectively the lengths of the odd intervals $I_i$ and $I_{i+1}$ defined in Lemma 3; then when $1<i\le \lfloor \frac{\sqrt[6]{N}}{16}\rfloor$ , it holds $\frac{1}{2}{\Delta }_i<{\Delta }_{i+1}<{\Delta }_i$.

Lemma 5. (See in [8] ) Let ${\Delta }_0=\lfloor \frac{\sqrt{N}+1}{2}\rfloor$ be the length of the odd interval $I_0=\left[e_m^0,e_m^b\right]$ , ${\Delta }_1$ , ${\Delta }_2$ and ${\Delta }_3$ , be respectively the lengths of $I_1$ , $I_2$ and $I_3$ ; then ${\Delta }_1+{\Delta }_2+{\Delta }_3\Delta =\frac{1}{2}{\Delta }_0$ and when ${\Delta }_0\ge 26$ it holds ${\Delta }_1+{\Delta }_2>\frac{1}{4}{\Delta }_0$.

Lemma 6. (See in [8] ) If $k\ge \lfloor \sqrt[3\alpha ]{N^{\beta }}\rfloor$ for some positive integers $\beta \ge 1$ and $\alpha >\beta$ , then ${\Delta }_k$ is at most $\lfloor \frac{1}{4}\sqrt[2\alpha ]{N^{\alpha -\beta }}\rfloor$ ; otherwise it is at least $\lfloor \frac{1}{4}\sqrt[2\alpha ]{N^{\alpha -\beta }}\rfloor -1$

$\lfloor \frac{1}{4}\sqrt[2\alpha ]{N^{\alpha -\beta }}\rfloor -1$ . Particularly, arbitrary $\alpha \ge 2$ yields ${\Delta }_k\le \lfloor \frac{\sqrt[2\alpha ]{N}}{4}\rfloor$ for $k\ge \lfloor \sqrt[3\alpha ]{N^{\alpha -1}}\rfloor$ and ${\Delta }_k\ge \lfloor \frac{\sqrt[2\alpha ]{N}}{4}\rfloor -1$ for $k\le \lfloor \sqrt[3\alpha ]{N^{\alpha -1}}\rfloor -1$.

Lemma 7. (See in [8] ) Let $I_1\mathrm{,}{I}_2\mathrm{,}\cdots \mathrm{,}{I}_{\omega }$ be odd intervals defined in Lemma 3;

then there are intervals that contain at most $\lfloor \frac{\sqrt[4]{N}}{4}\rfloor$ nodes and there are intervals that contain at least $\lfloor \frac{\sqrt[4]{N}}{4}\rfloor -1$ nodes.

3. Algorithm Design and Numerical Experiments

Based on the previous lemmas, theorems and corollaries, one can easily draw the following conclusions.

1) If $N=pq$ is a semiprime, then there is a term $e_m^p$ that lies in the odd interval $I_0$ and satisfies $p=GCD\left(N,e_m^p\right)$ ;

2) If $I_0$ is subdivided into a series of subintervals that are defined in Lemma

3, then $e_m^p\in I_k$ with $k=\lfloor \frac{q}{p}\rfloor$ , and the bigger k is the fewer nodes are

contained in $I_k$ . Among all the subintervals, $I_1$ , $I_2$ and $I_3$ dominate half of

$I_0$ . Lemma 6 shows that, when $k\le \lfloor \sqrt[3\alpha ]{N^{\beta }}\rfloor -1$ there are at least $\lfloor \frac{1}{4}\sqrt[2\alpha ]{N^{\alpha -\beta }}\rfloor -1$ nodes in $I_k$.

These provide a guideline for designing new algorithm for integer factorization, as the following subsections demonstrates.

3.1. Strategy for Algorithm Design

Now it has gotten to know that finding $e_m^p$ out means a successful factorization of $N=pq$ . Since $e_m^p$ hides itself in one of $I_1\mathrm{,}{I}_2\mathrm{,}\cdots \mathrm{,}{I}_{\omega }$ , it can surely be found out by searching the intervals one by one. Considering by Lemma 7 that there are intervals that contain small number of nodes that can be searched in small time and there are also intervals that contain too many nodes to be searched when N is very big, it is necessary to know which intervals contain small number of nodes and which ones contain large number of nodes and then perform a brute-force search on the small ones and perform other searches on the large ones. Since the brute-force search is a time-consuming process, a Tolerable Number (TN) can be defined to be an upper bound of nodes that are sure to be searched out in a Tolerable Time (TM), which was introduced in FU’s article [9] . Obviously, Lemma 6 indicates that TN can be used to determine $\alpha$ by

$TN=\lfloor \frac{\sqrt[2\alpha ]{N}}{4}\rfloor$ and thus ${\omega }_0=\lfloor \sqrt[3\alpha ]{N^{\alpha -1}}\rfloor$ . Since the number of nodes in $I_{\omega }$ is

smaller than that in $I_{{\omega }_0}$ if $\omega >{\omega }_0$ by Lemma 6, TN is a critical number for the brute-force search. All the intervals $I_{{\omega }_0+1},I_{{\omega }_0+2},\cdots$ can be searched by the brute-force search.

Now it turns to the big intervals $I_1\mathrm{,}{I}_2\mathrm{,}\cdots \mathrm{,}{I}_{{\omega }_0}$ , each of which contains more than TN nodes. It is sure that, applying TN to subdivide each of these big intervals can obtain a series of new small odd intervals and then assigning each of the newly-subdivided small subintervals a process in a parallel computing system can perform the brute-force search in TM, as tested by FU [9] . However, this might require huge computing resources. For example, FU’s approach took more than 8 days to factorize a big number of 46-decimaldigits on Chinese Tianhe Supper Computer with 392 processes. On the other hand, by Lemma 3, there is a big probability to find the objective node when applying a probabilistic approach. Thus it is worthy of trying a probabilistic search.

By now, setting a TN, calculating an $\alpha$ by $TN=\lfloor \frac{\sqrt[2\alpha ]{N}}{4}\rfloor$ plus an $\omega$ by $\omega =\lfloor \sqrt[3\alpha ]{N^{\alpha -1}}\rfloor$ and imagining varying $k=\lfloor \frac{q}{p}\rfloor$ result in a subdivision of the

interval $I_0$ into two kinds of subintervals, the kind of small ones and the kind of big ones, as shown in Figure 2. Each of the small ones contains no more than TN nodes and can be searched by the brute-force search while each of the big ones contains more than TN nodes that need probabilistic searching approaches to search.

Now consider a big odd subinterval I that contains n terms. Suppose the objective odd number $o=ps$ lies at the m-th position. Referring to the analysis in [10] , it knows that, choosing randomly k ( $k<m$ ) terms on the left of o, say $o_{-j}\mathrm{,}\cdots \mathrm{,}{o}_{-j-1}\mathrm{,}{o}_{-j-k}$ , and their respectively symmetric terms on the right of o, namely, $o_j\mathrm{,}{o}_{j+1}\mathrm{,}\cdots \mathrm{,}{o}_{j+k}$ , yields $o_{-j-k}+\cdots +o_{-j-1}+o_{-j}+o_j+o_{j+1}+\mathrm{...}+o_{j+k}=2ko$ with $j=1,2,\cdots ,m-k-1$ . Therefore, choosing in I randomly 2k terms and adding the chosen terms might obtain o in big probability, as proved in [10] . With the help of multi-dimensional random-number generator, as introduced in [11] , it is easy to pick 2k random terms in I. Considering the case that o lies near the start-position or the end-position of the interval I might fail to pick the necessary number of terms, it is reasonable to make near I’s ends one or more small subintervals each of which contain TN of nodes. These small subintervals are called TN intervals and they can be searched in TM with brate-force searches. The remained part of I is called a probabilistic intervals, as shown in Figure 3. Such a subdivision that includes two TN intervals near the ends and a probabilistic interval in the middle is called a TNPTN subdivision. With the TNPTN subdivision, it is necessary to perform brute-force searches on the two TN intervals and a probabilistic search on the whole interval I.

3.2. TNPTN Parallel Probabilistic Algorithm

Based on the strategy for algorithm design stated in previous section, a parallel algorithm, which is called TNPTN MPI Algorithm, is designed to find an

objective node $N_{obj}$ that has common divisor p with $N=pq$ . The algorithm assumes that $k=\lfloor q/p\rfloor$ varies from 1 to an upper bound and assigns for each k a process to search $N_{obj}$ . It requires initial input data N to be the big semiprime, TN to be the number of the maximal steps that a brute-force search performs and a number $N_{rand}$ with $N_{rand}<TN$ to set the number of random odd integers that are randomly picked in its searched interval with the multi-dimensional random-number generator introduced in [11] . It also requires a brute-force searching subroutine and a probabilistic searching subroutine to perform the operations.

3.3. Numerical Experiments

Numerical experiments were made on a Sugon workstation with Xeon(R) E5-2650 V3 processor of 20 cores and 128GB memory via C++ MPI programming with gmp big number library. Several big semiprimes with 27 to 46 decimal-digits are factorized, as shown in Table 1.

4. Conclusion and Future Work

It is a convention to make a comparison of a new approach to the old ones although, sometime, there is no comparability between two things. Accordingly, this section makes comparisons and then prospects some future work.

It can see from the implementation of algorithms list in previous section that, each of the algorithms 1, 2 and 3 needs memory only for storing a few integers to be taken into the computation. They cost less memory. Since the whole procedure is a parallel one, the time it costs depends on the resources joining the computation. Theoretically, it is at most $O\left(2\sqrt[4]{N}{\left(lo{g}_{2}N\right)}^3\right)$ bit-operations

providing that there is $\lfloor \frac{\sqrt[4]{N}}{2}\rfloor$ process joining the computation.

Now turn to the old ones. It is known that, ever since John Pollard raised in 1975 his Pollard’s Rho algorithm, which is a probabilistic algorithm and is efficient in factoring small integers, many algorithms of integer factorization have developed. As stated in the introductory section, the GNFS has been regarded the fastest approach to factorize big integers under both sequential and parallel computing and almost all the factorized RSA numbers are factorized by the approach with parallel computing. So here the new approach is merely compared to the Pollard’s Rho approach and the GNFS approach.

First compare with the Pollard’s Rho approach. From the point-view of memory cost, the new approach is like the Pollard’s Rho approach that costs less memory. From the point-view of time consumption, the two are almost the same efficiency according to the experiments in articles [6] and [12] . However, as pointed out in article [13] , the Pollard’s Rho approach cannot be parallelised. Actually, this article is the first one that proposes a parallel probabilistic approach in factoring integers.

Next compare with the GNFS approach. The GNFS approach is a deterministic one that can be parallelised. As article [14] has pointed out, GNFS requires a large amount of memory. Hence from the point-view of memory cost, the new approach is superior to the GNFS. From the point-view of time consumption, the comparison cannot be available because the new approach has not been applied on the many computers as the GNFS used in factoring large RSA numbers. Nevertheless, it can see from the experiments of factoring the 46 decimal bits semiprime that, one computer of 20 cores can factorize it in 3 days.

There is another approach stated by Kurzweg U H [15] . Seeing from his series of Blogs, one can see that Kurzweg actually tried to find out $\varphi \left(N\right)$ to factorize the semiprime N. The idea was early seen in chapter 6 of YAN’s book [1] . Actually, it is quite occasional for Kurzweg’s to factorize the numbers he reported because he has not brought an approach that finds out $\varphi \left(N\right)$ inevitably.

By now it can see that, the approach raised in this article is surely worthy of investigation because it is truly derived from the theorems and corollaries that are proved mathematically. In spite that the new approach is less of successful cases of factoring the RSA numbers, it does factorize many odd integers as many old approaches did in the history. As a new approach, it leaves of course quite a lot of researches to improve and perfect. For example, the probabilistic searching procedure is very rough and needs improving, and the time complexity of the algorithm has not be evaluated till now for its probabilistic trait and also for the authors’ limitation of the required knowledge. This points out the study of the future work. Hope it is concerned more and successful in the future.

Acknowledgements

The research work is supported by the State Key Laboratory of Mathematical Engineering and Advanced Computing under Open Project Program No.2017A01, Department of Guangdong Science and Technology under project 2015A030401105, Foshan Bureau of Science and Technology under projects 2016AG100311, Project gg040981 from Foshan University. The authors sincerely present thanks to them all.

Cite this paper

Li, J.H. (2018) A Parallel Probabilistic Approach to Factorize a Semiprime. American Journal of Computational Mathematics, 8, 175-183. https://doi.org/10.4236/ajcm.2018.82013

References