Find a divisor satisfying a given congruence

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.

• 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? – Zander May 18 '13 at 13:18
• @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. – vadim123 May 18 '13 at 14:24