Suppose I have a highly composite positive integer $N$ with at least $10^{15}$ divisors for which I know the prime factorization.

Given $M$ with $\gcd(M,N)=1$ is there an efficient way to find a divisor $d|N$ with $d>1$ and $d\equiv 1 \pmod{M}$?

(If necessary assume one exists, or if possible determine whether one exists give $N,M$.)

By efficient I'm hoping for something $o(M+\sigma_0(N))$ where $\sigma_0(N)$ is the number of divisors of $N$.

As a concrete example, does $100!$ have a divisor $d>1$ with $d\equiv 1 \pmod{1999\times 2003\times 2011}$?


Coppersmith et al. give an algorithm based on LLL lattice reduction in a paper Divisors in Residue Classes, Constructively (2004) that solves this problem if $M$ is not too small relative to N, specifically $M>N^{1/4}$.

For the given example I was able to find a divisor a different way. Since here $M=1999\cdot 2003\cdot 2011=P_1P_2P_3$ can be written as a product of a few small factors, we can proceed as follows. Write $N=N_1 N_2 \cdots N_K$ with $\sigma_0(N_1)\approx \sigma_0(N_2)\approx \sigma_0(N)^{1/K}$. (This can be done by finding the prime factorization of $N=p_1^{a_1}p_2^{a_2}\ldots p_j^{a_j}$ and splitting off groups with $\prod (a_i+1)$ of approximately the desired size, with further refinements possible depending on the level of precision desired.)

By enumerating the factors of $N_k$ construct the sets $$ S_k = \{t~;~t\mid N_k \quad\mathrm{and}\quad t\equiv 1 \pmod{P_1}\} $$ Then for any choice of $t_i\in S_i, t_j\in S_j, i\ne j$ we have $t_i t_j \mid N$ and $t_i t_j \equiv 1 \pmod{P_1}$.

We could take the $S_i$ in pairs and construct sets $\{t_i t_j \equiv 1 \pmod{P_1 P_2}\}$, and repeat for each factor of $M$ (as long as some of the sets are not empty). But in this case $M/P_1$ is small enough, so we can just try all $\prod t_i$ until we find some with $\prod t_i \equiv 1 \pmod{M/P_1}$, which is likely to happen by the time we've tried on the order of $M/P_1$ possibilities.

Here I can take $K=3, N_1=2^{32}3^{48}5^{24}7^{16}11^9,N_2=2^{25}13^7 17^5 19^5 23^4 29^3 31^3 37^2$, then I get $\lvert S_1\rvert=3420,\lvert S_2\rvert=900,\lvert S_3\rvert=562$, and trying some of the possible $t_1 t_2 t_3$ I find, for example, $$ d = 2^{62} 3^3 5^2 7\cdot 11\cdot 13 \cdot 17^3 23^2 29 \cdot 37^2 47^2 53 \cdot 61 \cdot 73 \cdot 83 \\ $$ or $$ d = 2^{38}3^5 7 \cdot 11^7 13^7 \cdot 17\cdot 23 \cdot 29^3 31^3 37^2 43 \cdot 47^2 53 \cdot 59 \cdot 73 \cdot 83 \cdot 89 $$ which satisfy the congruence.

Unfortunately this approach would not work if $M$ were a prime number of a similar magnitude.


I don't know if this is the sort of thing you're looking for, but here is an algorithm that will take $O(M\phi(M))$ time, and require $O(M)$ storage. We have $N=p_1^{a_1} p_2^{a_2}\cdots p_k^{a_k}$, but instead we take each prime modulo $M$, to give us $r_1^{b_1}r_2^{b_2}\cdots r_s^{b_s}$, where the $r_i$'s are residue classes. We store an array of size $M$. A zero indicates that residue class has yet to be achieved; otherwise we store information about how to get that residue class from $N$, e.g. the exponents of the $r_i$'s. The general loop is, for the first $r_i$, we represent $r_i$ alone. Then, we cycle through the entire array, multiplying each entry by $r_i$, and putting the new result in the array. We repeat this $b_i-1$ times, and then move to $r_{i+1}$. We exit immediately if we get residue class 1. Worst case scenario, it will take $\phi(M)$ steps because that's $|\mathbb{Z}_M^\times|$, and each time we have to go through the whole array.

  • $\begingroup$ In the worst case (we fail to find residue class 1), don't you end up effectively iterating over all divisors of $N$, visiting other residue classes multiple times? $\endgroup$ – Zander May 18 '13 at 13:18
  • $\begingroup$ @Zander, this is true only of each prime is smaller than $M$ -- the savings comes from reducing $p_i$ to $r_i$. But in that case $M$ is "large", so we would expect few divisors of $N$ will work and hence searching for a particular one might involve searching all of them. $\endgroup$ – vadim123 May 18 '13 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.