Potentially new approach to factoring big numbers

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

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$.

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.$$