On $r$ -th Root Extraction Algorithm in $\mathbb {F}_q$ for $q\equiv lr^{s}+1\;({\mathrm mod}\; r^{s+1})$ $0< l< r$ $s$
| Autor: | Gook Hwa Cho, Soonhak Kwon, Namhun Koo |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Exponentiation Root of unity Computation Root (chord) Tonelli–Shanks algorithm 0102 computer and information sciences 02 engineering and technology 01 natural sciences 020202 computer hardware & architecture Theoretical Computer Science Combinatorics Finite field Computational Theory and Mathematics Integer 010201 computation theory & mathematics Hardware and Architecture Mod 0202 electrical engineering electronic engineering information engineering Software Mathematics |
| Zdroj: | IEEE Transactions on Computers. 65:322-325 |
| ISSN: | 0018-9340 |
| DOI: | 10.1109/tc.2015.2417562 |
| Popis: | We present an $r$ -th root extraction algorithm over a finite field $\mathbb {F}_q$ . Our algorithm precomputes a primitive $r^s$ -th root of unity $\xi$ 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|