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