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

Simple item page
dc.creatorZralek, Bartosz
dc.date2008-03-04
dc.date.accessioned2026-07-07T09:24:35Z
dc.date.available2026-07-07T09:24:35Z
dc.descriptionWe 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}+δ}$ for some arbitrary small $δ$. We also address the issue of computing roots modulo $p$ in deterministic time.
dc.description9 pages
dc.identifierhttps://arxiv.org/abs/0803.0471
dc.identifierhttp://arxiv.org/abs/0803.0471
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/156148
dc.subjectNumber Theory
dc.subject11Y16 (Primary); 11Y05 (Secondary)
dc.titleUsing the smoothness of p-1 for computing roots modulo p
dc.typetext

Files

Collections

arXiv