Back to Search
Start Over
On r -th Root Extraction Algorithm in Fq for q≡lrs+1(modrs+1) with 0<l<r and Small s.
- Source :
- IEEE Transactions on Computers; Jan2016, Vol. 65 Issue 1, p322-325, 4p
- Publication Year :
- 2016
-
Abstract
- We present an r<alternatives> <inline-graphic xlink:type="simple" xlink:href="kwon-ieq6-2417562.gif"/></alternatives>-th root extraction algorithm over a finite field \mathbb {F}_q<alternatives> <inline-graphic xlink:type="simple" xlink:href="kwon-ieq7-2417562.gif"/></alternatives>. Our algorithm precomputes a primitive r^s$<alternatives><inline-graphic xlink:type="simple" xlink:href="kwon-ieq8-2417562.gif"/> </alternatives>-th root of unity $\xi$<alternatives> <inline-graphic xlink:type="simple" xlink:href="kwon-ieq9-2417562.gif"/></alternatives> where $s$<alternatives><inline-graphic xlink:type="simple" xlink:href="kwon-ieq10-2417562.gif"/></alternatives> is the largest positive integer satisfying $r^s| q-1$<alternatives> <inline-graphic xlink:type="simple" xlink:href="kwon-ieq11-2417562.gif"/></alternatives>, and is applicable for the cases when $s$<alternatives><inline-graphic xlink:type="simple" xlink:href="kwon-ieq12-2417562.gif"/> </alternatives> is small. The proposed algorithm requires one exponentiation for the $r$<alternatives><inline-graphic xlink:type="simple" xlink:href="kwon-ieq13-2417562.gif"/></alternatives> -th root computation and is favorably compared to the existing algorithms. [ABSTRACT FROM AUTHOR]
- Subjects :
- DATA extraction
COMPUTER software
COMPUTER algorithms
CRYPTOGRAPHY
DATA mining
Subjects
Details
- Language :
- English
- ISSN :
- 00189340
- Volume :
- 65
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Computers
- Publication Type :
- Academic Journal
- Accession number :
- 111881851
- Full Text :
- https://doi.org/10.1109/TC.2015.2417562