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.
Best Answer
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=13229If increase vector
Vto10^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))))Then how select $b$?
Let
b=3*5*7*29*37*47*83*2713;z%b=13229Step 3 is very simple, if will simple factorizable
b*(z\b+-k)+13229, wherek=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/2to1and findx,y:forstep(i=#D/2,1,-1,x=D[i];y=d/x;print("x= "x"; y= "y))=But how this help get factors of $z$ in Step 4?
Note:
lift(Mod(13229,z)^(z-1))%13229=11789and
znorder(Mod(13229,z))%13229=11789If 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