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