Taking Roots over High Extensions of Finite Fields

Details Taking Roots over High Extensions of Finite Fields Taking Roots over High Extensions of Finite Fields

2011-10-19

arxiv.org/abs/1110.4350v1

Computer Science

Data Structures and Algorithms

Scientific paper

We present a new algorithm for computing $m$-th roots over the finite field $\F_q$, where $q = p^n$, with $p$ a prime, and $m$ any positive integer. In the particular case $m=2$, the cost of the new algorithm is an expected $O(\M(n)\log (p) + \CC(n)\log(n))$ operations in $\F_p$, where $\M(n)$ and $\CC(n)$ are bounds for the cost of polynomial multiplication and modular polynomial composition. Known results give $\M(n) = O(n\log (n) \log\log (n))$ and $\CC(n) = O(n^{1.67})$, so our algorithm is subquadratic in $n$.

Affiliated with

Also associated with

No associations

Rating

Taking Roots over High Extensions of Finite Fields 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 Taking Roots over High Extensions of Finite Fields, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Taking Roots over High Extensions of Finite Fields will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-597883