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

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

2008-03-04

arxiv.org/abs/0803.0471v1

Mathematics

Number Theory

9 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Using the smoothness of p-1 for computing roots modulo p does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Using the smoothness of p-1 for computing roots modulo p, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using the smoothness of p-1 for computing roots modulo p will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-406448