Using the smoothness of p-1 for computing roots modulo p

Abstract

We prove, without recourse to the Extended Riemann Hypothesis, that the projection modulo $p$ of any prefixed polynomial with integer coefficients can be completely factored in deterministic polynomial time if $p-1$ has a $(\ln p{)}^{O(1)}$-smooth divisor exceeding $(p-1{)}^{1/2+\delta }$ for some arbitrary small $\delta$. We also address the issue of computing roots modulo $p$ in deterministic time.

9 pages

Cited by in corpus (1)

• A deterministic version of Pollard's p-1 algorithm