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

(l n p)^{O (1)}

-smooth divisor exceeding

(p - 1)^{1 / 2 + d e l t a}

for some arbitrary small

d e l t a

. We also address the issue of computing roots modulo

p

in deterministic time.

This page was built for publication: Using the smoothness of p-1 for computing roots modulo p