Paper 2013/117

On r-th Root Extraction Algorithm in F_q For q=lr^s+1 (mod r^(s+1)) with 0 < l < r and Small s

Namhun Koo, Gook Hwa Cho, and Soonhak Kwon

Abstract

We present an r-th root extraction algorithm over a finite field F_q. Our algorithm precomputes a primitive r^s-th root of unity where s is the largest positive integer satisfying r^s| q-1, and is applicable for the cases when s is small. The proposed algorithm requires one exponentiation for the r-th root computation and is favorably compared to the existing algorithms.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Unknown where it was published
Keywords
r-th root algorithmfinite fieldAdleman-Manders-Miller algorithmCipolla-Lehmer algorithm
Contact author(s)
shkwon7 @ gmail com
History
2013-02-27: received
Short URL
https://ia.cr/2013/117
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/117,
      author = {Namhun Koo and Gook Hwa Cho and Soonhak Kwon},
      title = {On r-th Root Extraction Algorithm in F_q For q=lr^s+1 (mod r^(s+1)) with 0 < l < r and Small s},
      howpublished = {Cryptology ePrint Archive, Paper 2013/117},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/117}},
      url = {https://eprint.iacr.org/2013/117}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.