Improvement Of Barreto-Voloch Algorithm For Computing $r$th Roots Over Finite Fields

Details Improvement Of Barreto-Voloch Algorithm For Computing $r$th Roots Over Finite Fields Improvement Of Barreto-Voloch Algorithm For Computing $r$th Roots Over Finite Fields

2011-10-19

arxiv.org/abs/1110.4801v1

Computer Science

Symbolic Computation

Scientific paper

Root extraction is a classical problem in computers algebra. It plays an essential role in cryptosystems based on elliptic curves. In 2006, Barreto and Voloch proposed an algorithm to compute $r$th roots in ${F}_{q^m} $ for certain choices of $m$ and $q$. If $r\,||\,q-1$ and $ (m, r)=1, $ they proved that the complexity of their method is $\widetilde{\mathcal {O}}(r(\log m+\log\log q)m\log q) $. In this paper, we extend the Barreto-Voloch algorithm to the general case that $r\,||\,q^m-1$, without the restrictions $r\,||\,q-1$ and $(m, r)=1 $. We also specify the conditions that the Barreto-Voloch algorithm can be preferably applied.

Affiliated with

Also associated with

No associations

Rating

Improvement Of Barreto-Voloch Algorithm For Computing $r$th Roots Over 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 Improvement Of Barreto-Voloch Algorithm For Computing $r$th Roots Over Finite Fields, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improvement Of Barreto-Voloch Algorithm For Computing $r$th Roots Over Finite Fields will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-598047