Name
Abstract | ||
|---|---|---|
Let F_q be a finite field with q elements with prime power q and let r>1 be an integer with $q\equiv 1 \pmod{r}$. In this paper, we present a refinement of the Cipolla-Lehmer type algorithm given by H. C. Williams, and subsequently improved by K. S. Williams and K. Hardy. For a given r-th power residue c in F_q where r is an odd prime, the algorithm of H. C. Williams determines a solution of X^r=c in $O(r^3\log q)$ multiplications in F_q, and the algorithm of K. S. Williams and K. Hardy finds a solution in $O(r^4+r^2\log q)$ multiplications in F_q. Our refinement finds a solution in $O(r^3+r^2\log q)$ multiplications in F_q. Therefore our new method is better than the previously proposed algorithms independent of the size of r, and the implementation result via SAGE shows a substantial speed-up compared with the existing algorithms. |
Year | Venue | Field |
|---|---|---|
2015 | CoRR | Integer,Prime (order theory),Combinatorics,Finite field,Algorithm,Prime power,Mathematics |
DocType | Volume | Citations |
Journal | abs/1501.04036 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Namhun Koo | 1 | 3 | 5.76 |
| Gook Hwa Cho | 2 | 2 | 3.03 |
| Byeonghwan | 3 | 0 | 0.34 |
| Soonhak Kwon | 4 | 170 | 22.00 |