Divisors in Residue Classes Revisited

Jonathon Hales

In 1984, H. W. Lenstra described an algorithm finding divisors of $N$ congruent to $r\mathrm{mod}S$. When $S^3>N$, this algorithm runs in polynomial time and hence factors $N$ in time…