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
-
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},
url = {https://eprint.iacr.org/2013/117}
}
