Potentially new approach to factoring big numbers

Question

Update on 5/27/2020: I summarized all discussions related to this post, added a bit more about computational complexity, and published it on my blog, here.

I've been working on this problem for a long time, read great books on the topic, and came up with the following. I am wondering if my approach could result in a very fast algorithm for factoring big numbers.

1. Algorithm

As an illustration of how it works, let's apply it to factoring a very modest number, $z=x\cdot y = 1223 \times 2731$. It involves the following steps.

Step 1. Compute $z_p = z \mbox{ Mod } p$, for $p=2, 3, 5, 7, 9, 11, 13,\cdots, p_z$. In this case, the upper bound can be as low as $p_z = 127$ (see section 2 about the choice of $p_z$). Check values of $p$ generating many identical $z_p$ values. Here, $z_p = 5$ or $z_p = 23$ for instance.

Step 2. We have $z_{59} = z_{85} = z_{111} = 23$. Thus if $b = 59 \times 85 \times 111$, because of Theorem A listed below, we have $z_b=23$. Not sure if this is of any help.

Step 3. Find the set of $(x, y)$ with $x<y$, with $x, y$ odd, and $x\cdot y \leq z$ satisfying all of the following:

• $x\cdot y = 23 \mbox{ Mod } 59$
• $x\cdot y = 23 \mbox{ Mod } 85$
• $x\cdot y = 23 \mbox{ Mod } 111$

You need to create 3 multiplication tables to identify the full list (intersection of 3 infinite lists) of candidates, and ignore those $(x, y)$ that result in $x\cdot y> z$ or $x$ even or $y$ even.

Step 4. The result is $(x, y) \in \{(61,36503),(173,12871),(211,10553),(829, 1327),(1223,2731) \}$.

Step 5. Among all the 5 above candidates, check if one yields $x\cdot y = z$. Here $(x=1223, y=2731)$ does and we've factored $z$.

The big question is: how difficult it is to perform step 3? The following elementary theorem could be useful. Could you find a reference for this theorem, or at least prove it? I discovered it myself, but I am sure it must be at least 300 years old.

Theorem A

Let $p_1, \cdots, p_k$ be $k$ pairwise co-prime positive integers, and $a>0$ an integer. If $z= a \mbox{ Mod } p_i$ for $i=1,\cdots,k$, then $z= a \mbox{ Mod } (p_1\cdots p_k)$. Also, let $$q = \arg \max_{p<z} \{z= a \mbox{ Mod } p\}.$$
Then $q+a = z$.

2. Choice of $p_z$

In practice, in step 1, you can choose the smallest $p_z$ such that $2\cdot 3 \cdot 5\cdot 7 \cdots \cdot p_z > M z$ where $M$ is an absolute constant, maybe as low as $M=30$.

Then you have more than enough choices for step 3. In our example in section 1, we have $z= 3,340,013$ while $59\times 85 \times 111 = 556,665$. It results in only 5 candidates in step 4.

If instead, we consider

• $x\cdot y = 5 \mbox{ Mod } 21$
• $x\cdot y = 5 \mbox{ Mod } 47$
• $x\cdot y = 23 \mbox{ Mod } 59$
• $x\cdot y = 23 \mbox{ Mod } 85$
• $x\cdot y = 23 \mbox{ Mod } 111$

then there would be only 1 candidate in step 4, resulting in factoring $z$. Note that the product $21 \times 47 \times 59\times 85 \times 111 =549,428,355$ is big enough (much bigger than $z$ itself) and this is what causes the candidate in step 4 to be unique, thus removing the need for step 5.

Another example also producing a single candidate (the correct one) is

• $x\cdot y = 2 \mbox{ Mod } 3$
• $x\cdot y = 3 \mbox{ Mod } 5$
• $x\cdot y = 5 \mbox{ Mod } 7$
• $x\cdot y = 6 \mbox{ Mod } 11$
• $x\cdot y = 1 \mbox{ Mod } 13$
• $x\cdot y = 6 \mbox{ Mod } 17$
• $x\cdot y = 3 \mbox{ Mod } 19$

Again only one candidate in step 4 (thus no step 5) because $3\times 5 \times 7 \cdots \times 19 = 4,849,845$ is big enough, bigger than $z$.

3. Working with non-primes and conjecture

Weirdly enough, this choice works too, resulting in 4 candidates in step 4, including the correct one:

• $x\cdot y = 1242861 \mbox{ Mod } 2^{21}$

The result is $(x, y) \in \{(3,414287),(97,12813),(291,4271),(1223,2731) \}$. Remember, $z = 1223 \times 2731$.

This leads to the following conjecture.

Conjecture

If $z$ is not a prime number, then the following system, with $x \cdot y \leq z$, uniquely determines two non-trivial numbers $x, y$ such that $x\cdot y = z$. The system is as follows:

$$x\cdot y = m_i \mbox{ Mod } p_i, \mbox{ with } i=1,\cdots, k$$ where $p_1,p_2$ and so on are the prime numbers, $m_i = z \mbox{ Mod } p_i$, and $k$ is the smallest integer such that $p_1\times \cdots\times p_k > C z$ where $C$ is an absolute constant. I don't know what would be the lower bound for $C$, maybe $C=10$ works.

The congruence system is linked to the Chinese Remainder Theorem. See page 88 in the book Prime Numbers - A Computational Perspective (2nd Edition), by R Grandall and C Pomerance (Springer, 2010). A careful choice of the moduli (rather than $p_1, \cdots, p_k$) could lead to a faster algorithm.

Answer 1

Only comment and some questions.

Let $z=24!-1$.

z=24!-1;print(factorint(z))=[625793187653, 1; 991459181683, 1]

Find $z_p$:

V=vector(10^5);forstep(m=3,#V,2,r=z%m;V[r]+=1);vecmax(V,&zp);zp=13229

If increase vector V to 10^7, it will also $z_p=13229$

But if $z$ will be really big as 2000 bit, how find $z_p$?

Find prime factors of $b$:

print(factorint(z-13229))=

[2, 1; 3, 3; 5, 1; 7, 2; 29, 1; 37, 1; 47, 2; 83, 1; 2713, 1; 87866333, 1]

Other way:

forstep(m=3,10^5,2,r=z%m;if(r==13229,print(m" "factorint(m))))

13565    [5, 1; 2713, 1]
14805    [3, 2; 5, 1; 7, 1; 47, 1]
15355    [5, 1; 37, 1; 83, 1]
15463    [7, 1; 47, 2]
15651    [3, 2; 37, 1; 47, 1]
15687    [3, 3; 7, 1; 83, 1]
16095    [3, 1; 5, 1; 29, 1; 37, 1]
16317    [3, 2; 7, 2; 37, 1]
16849    [7, 1; 29, 1; 83, 1]
18991    [7, 1; 2713, 1]
19505    [5, 1; 47, 1; 83, 1]
19881    [3, 2; 47, 2]
20335    [5, 1; 7, 2; 83, 1]
20445    [3, 1; 5, 1; 29, 1; 47, 1]
20727    [3, 2; 7, 2; 47, 1]
21315    [3, 1; 5, 1; 7, 2; 29, 1]
21497    [7, 1; 37, 1; 83, 1]
21663    [3, 2; 29, 1; 83, 1]
22533    [3, 1; 7, 1; 29, 1; 37, 1]
24417    [3, 2; 2713, 1]
26085    [3, 1; 5, 1; 37, 1; 47, 1]
26145    [3, 2; 5, 1; 7, 1; 83, 1]
27195    [3, 1; 5, 1; 7, 2; 37, 1]
27307    [7, 1; 47, 1; 83, 1]
27405    [3, 3; 5, 1; 7, 1; 29, 1]
27639    [3, 2; 37, 1; 83, 1]
28623    [3, 1; 7, 1; 29, 1; 47, 1]
28971    [3, 3; 29, 1; 37, 1]
33135    [3, 1; 5, 1; 47, 2]
34545    [3, 1; 5, 1; 7, 2; 47, 1]
34965    [3, 3; 5, 1; 7, 1; 37, 1]
35109    [3, 2; 47, 1; 83, 1]
36105    [3, 1; 5, 1; 29, 1; 83, 1]
36519    [3, 1; 7, 1; 37, 1; 47, 1]
36603    [3, 2; 7, 2; 83, 1]
36801    [3, 3; 29, 1; 47, 1]
37555    [5, 1; 7, 1; 29, 1; 37, 1]
38367    [3, 3; 7, 2; 29, 1]
40695    [3, 1; 5, 1; 2713, 1]
44415    [3, 3; 5, 1; 7, 1; 47, 1]
46065    [3, 1; 5, 1; 37, 1; 83, 1]
46389    [3, 1; 7, 1; 47, 2]
46953    [3, 3; 37, 1; 47, 1]
47705    [5, 1; 7, 1; 29, 1; 47, 1]
48285    [3, 2; 5, 1; 29, 1; 37, 1]
48951    [3, 3; 7, 2; 37, 1]
50431    [29, 1; 37, 1; 47, 1]
50547    [3, 1; 7, 1; 29, 1; 83, 1]
52577    [7, 2; 29, 1; 37, 1]
56973    [3, 1; 7, 1; 2713, 1]
58515    [3, 1; 5, 1; 47, 1; 83, 1]
59643    [3, 3; 47, 2]
60865    [5, 1; 7, 1; 37, 1; 47, 1]
61005    [3, 1; 5, 1; 7, 2; 83, 1]
61335    [3, 2; 5, 1; 29, 1; 47, 1]
62181    [3, 3; 7, 2; 47, 1]
63945    [3, 2; 5, 1; 7, 2; 29, 1]
64061    [29, 1; 47, 2]
64491    [3, 1; 7, 1; 37, 1; 83, 1]
64989    [3, 3; 29, 1; 83, 1]
66787    [7, 2; 29, 1; 47, 1]
67599    [3, 2; 7, 1; 29, 1; 37, 1]
73251    [3, 3; 2713, 1]
77315    [5, 1; 7, 1; 47, 2]
78255    [3, 2; 5, 1; 37, 1; 47, 1]
78435    [3, 3; 5, 1; 7, 1; 83, 1]
78677    [29, 1; 2713, 1]
81585    [3, 2; 5, 1; 7, 2; 37, 1]
81733    [37, 1; 47, 2]
81921    [3, 1; 7, 1; 47, 1; 83, 1]
82917    [3, 3; 37, 1; 83, 1]
84245    [5, 1; 7, 1; 29, 1; 83, 1]
85211    [7, 2; 37, 1; 47, 1]
85869    [3, 2; 7, 1; 29, 1; 47, 1]
89059    [29, 1; 37, 1; 83, 1]
94955    [5, 1; 7, 1; 2713, 1]
99405    [3, 2; 5, 1; 47, 2]

Then how select $b$?

Let b=3*5*7*29*37*47*83*2713;

z%b=13229

Step 3 is very simple, if will simple factorizable b*(z\b+-k)+13229, where k=1,2,3,..

Example:

d=b*(z\b-1)+13229;D=divisors(d)=

[1, 2, 117973, 235946, 67324261, 134648522, 39059030209, 78118060418, 7942445042953, 15884890085906, 4607910970846357, 9215821941692714, 2629620344197600549, 5259240688395201098, 310224200866023529567177, 620448401732047059134354]

Downstep from #D/2 to 1 and find x,y:

forstep(i=#D/2,1,-1,x=D[i];y=d/x;print("x= "x"; y= "y))=

x= 78118060418;  y= 7942445042953
x= 39059030209;  y= 15884890085906
x= 134648522;  y= 4607910970846357
x= 67324261;  y= 9215821941692714
x= 235946;  y= 2629620344197600549
x= 117973;  y= 5259240688395201098
x= 2;  y= 310224200866023529567177
x= 1;  y= 620448401732047059134354

But how this help get factors of $z$ in Step 4?

---

Note:

lift(Mod(13229,z)^(z-1))%13229=11789

and

znorder(Mod(13229,z))%13229=11789

If check other remainders wich not equal $13229$, then this not performed, for example:

lift(Mod(13241,z)^(z-1))%13241!=znorder(Mod(13241,z))%13241

Answer 2

A more general conjecture is this, it is I believe actually a theorem - the Chinese Remainder Theorem indeed:

If $z$ is not a prime number, then the following system, with $x\cdot y \leq z$, uniquely determines two non-trivial numbers $x,y$ such that $x \cdot y=z$. The system is as follows:

$$x \cdot y=m_i \mbox{ Mod } p_i, \mbox{ with } i=1\cdots ,k$$ where $p_1,p_2$ and so on are pairwise co-prime, $m_i=z \mbox{ Mod } p_i$, and $k$ is such that $p_1 \times \cdots \times p_k> z$. As an example with the same $z = 1223 \times 2731$, take two co-prime moduli $p_1, p_2$ very close to $\sqrt{z}$ and it works. For instance, with $p_1 = 1827, p_2=1829$:

• $x\cdot y = 257 \mbox{ Mod } 1827$
• $x\cdot y = 259 \mbox{ Mod } 1829$

There is only one solution to this, it's $x=1223, y=2731$, revealing two factors of $z$. Now I don't know how likely two integers close to $\sqrt{z}$ are going to be co-prime. There is an interesting consequence to this.

Ignore the fact that we want to factor $z$, but think instead that we are only interested in solving $x \cdot y = m \mbox{ Mod } z$, with $m = 0$. The difficulty of this problem is caused by $z$ (if $z$ is large), not by $m$. Say that computational complexity is $O(f(z))$ for some function $f$. In my example, I reduced computational complexity to essentially $O(2f(\sqrt{z}))$.

Instead of using two co-prime close to $\sqrt{z}$, you could use four pairwise co-prime close to $z^{1/4}$, for instance:

• $x\cdot y = 30 \mbox{ Mod } 41$
• $x\cdot y = 31 \mbox{ Mod } 43$
• $x\cdot y = 23 \mbox{ Mod } 45$
• $x\cdot y = 5 \mbox{ Mod } 47$

Again, only one solution to this (with $x\cdot y \leq z, x< y$): $x=1223, y=2731$. In this case, we reduced computational complexity from $O(f(z))$ to $O(4f(z^{1/4}))$.

How to choose $p_1,\cdots,p_k$ so that they are co-prime?

In our example with $k=2, p_1=1827, p_2=1829$, we did not check whether $p_1$ and $p_2$ were coprime. By chance, they happen to be. In order to significantly increase the odds to pick up co-prime numbers, we could have chosen $p_1=2\cdot 3\cdot 5\cdot 7\cdot q_1 + 1$ and $p_2=11\cdot 13\cdot q_2 + 2$, where $q_1, q_2$ are as small as possible yet satifying $p_1 \cdot p_2 > z$.Here $q_1 = 9$ and $q_2 = 13$ works, resulting in $p_1 = 1891$ and $p_2=1861$. Again this leads to a unique (correct) solution in step 4. And by construction, we know that $p_1,p_2$ do not share any of $2, 3, 5, 7, 11, 13$ as common divisors, making it much more likely that they are co-prime (indeed, they are). In this case, $x,y$ satisfy

• $x\cdot y = 507 \mbox{ Mod } 1891$
• $x\cdot y = 1379 \mbox{ Mod } 1861$

The only solution with $x\cdot y\leq z$ and $x< y$ is again $x=1223, y =2731$. Again, $x\cdot y = z$. The probability that two numbers not sharing $2, 3, 5, 7, 11, 13$ as common divisors are co-prime, is

$$1 + \prod_{p\leq13} \Big(1-\frac{1}{p^2}\Big) - \prod_{p\geq 2 } \Big(1-\frac{1}{p^2}\Big) = 1 -\frac{6}{\pi^2} + \prod_{p\leq 13} \Big(1-\frac{1}{p^2}\Big)\approx 99\%$$

where the products are over primes. See also here for more about this. Likewise (see here and here), the probability that $k$ numbers not sharing $2, 3, 5, 7, 11, 13$ as common divisors are co-prime (though not necessarily pairwise coprime), is

$$ 1 -\frac{1}{\zeta(k)} + \prod_{p\leq 13} \Big(1-\frac{1}{p^k}\Big).$$

Note that all the lists (some really big) of candidates $(x, y)$ were obtained by semi-brute force, that is, $O(\sqrt{z})$. Without a good algorithm to solve the congruences and merge the lists, this technology is probably useless. Interesting, but not practical. In short, even though at first glance replacing factoring $z$ by solving a system of two congruences with moduli of the order $\sqrt{z}$ seems to drastically reduce computational complexity, in practice I don't know if there is any algorithm that can do it efficiently. Even though solving a system of two congruences is supposed to be an easier problem than solving $z=x\cdot y$.

Answer 3

This is a deeper dive to get more insights to solve step 3, indeed to simplify it to one equation with one variable. Lot's of work still need to be done to get an efficient algorithm.

Let's focus on the case $z=x\cdot y$ with

• $x\cdot y = m_1 \mbox{ Mod } p_1$
• $x\cdot y = m_2 \mbox{ Mod } p_2$

Here $p_1, p_2$ are co-prime, $p_1\cdot p_2 > z$. We further assume that $z$ is a product of two large primes, and that $p_1 \approx p_2 \approx \sqrt{z}$, so that $x< \min (p_1, p_2)$.

The above example with $z=3340013, p_1= 1891, p_2 = 1861$ is a typical case satisfying these requirements. It results, as discussed earlier, in $m_1 = 507, m_2 = 1379$. The solution is $x=1223, y=2731$. The methodology below uses that example as an illustration.

Let us denote as $g_p(y)$ the modular multiplicative inverse of $y$, modulo $p$. That is, $g_p(y)$ is uniquely defined by $1<g_p(y)<p$ and $y\cdot g_p(y) = 1 \mbox{ Mod } p$. This inverse exists if and only if $y$ and $p$ are co-prime. Then the above system with two variables $x, y$ and two congruences $x\cdot y = m_1 \mbox{ Mod } p_1$, $x\cdot y = m_2 \mbox{ Mod } p_2$ simplifies to one equation with one variable (unknown) $y$, as follows:

$$m_1 g_{p_1}(y) \mbox{ Mod } p_1 = m_2 g_{p_2}(y) \mbox{ Mod } p_2.$$

This is a strict equality, not a "modulo equality". The big challenge is how to solve this equation efficiently. Here we show that this equation is correct for our example. If $p_1 = 1891$, $p_2=1861$, $y=2731$, then we have $g_{p_1}(y) = 1416$ and $g_{p_2}(y)=1538$. We also have

$$507\cdot 1416 \mbox{ Mod } 1891 = 1223 = 1379\cdot 1538 \mbox{ Mod } 1861.$$

So the equation is satisfied. Note that $1223 = x$, the other factor of $z$. This is always the case. Also if you know $g_{p_1}(y)$, you can easily retrieve $y$ by performing another modular inversion: $y = g_{p_1}(g_{p_1}(y)) + n p_1$ where $n>0$ is a small integer assuming $x, y$ are relatively close to each other. In our case, $g_{p_1}(g_{p_1}(y))=g_{p_1}(1416) = 840$ and $n=1$, yielding $y=840 + 1891 = 2731$. Likewise, if you know $g_{p_2}(y)$, you can also retrieve $y$.

Note

Using the change of variable $u=g_{p_1}(y)$, that is $y=g_{p_1}(u) + n p_1$ (in most cases of interest including here, $n=1$), the main equation can be rewritten as

$$m_1 u \mbox{ Mod } p_1 = m_2 g_{p_2}(np_1+g_{p_1}(u)) \mbox{ Mod } p_2.$$