Name
Title | ||
|---|---|---|
New cube root algorithm based on the third order linear recurrence relations in finite fields |
Abstract | ||
|---|---|---|
In this paper, we present a new cube root algorithm in the finite field $$\mathbb {F}_{q}$$ F q with $$q$$ q a power of prime, which extends the Cipolla---Lehmer type algorithms (Cipolla, Un metodo per la risolutione della congruenza di secondo grado, 1903 ; Lehmer, Computer technology applied to the theory of numbers, 1969 ). Our cube root method is inspired by the work of Müller (Des Codes Cryptogr 31:301---312, 2004 ) on the quadratic case. For a given cubic residue $$c \in \mathbb {F}_{q}$$ c F q with $$q \equiv 1 \pmod {9}$$ q 1 ( mod 9 ) , we show that there is an irreducible polynomial $$f(x)$$ f ( x ) with root $$\alpha \in \mathbb {F}_{q^{3}}$$ F q 3 such that $$Tr\left( \alpha ^{\frac{q^{2}+q-2}{9}}\right) $$ T r q 2 + q - 2 9 is a cube root of $$c$$ c . Consequently we find an efficient cube root algorithm based on the third order linear recurrence sequences arising from $$f(x)$$ f ( x ) . The complexity estimation shows that our algorithm is better than the previously proposed Cipolla---Lehmer type algorithms. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s10623-013-9910-8 | Designs, Codes and Cryptography |
Keywords | Field | DocType |
Finite field,Cube root,Linear recurrence relation,Tonelli–Shanks algorithm,Cipolla–Lehmer algorithm,Adleman–Manders–Miller algorithm,11T06,11Y16,68W40 | Discrete mathematics,Tonelli–Shanks algorithm,Combinatorics,Finite field,Recurrence relation,Cube root,Algorithm,Irreducible polynomial,Mathematics,Number theory,Computer technology,Cube | Journal |
Volume | Issue | ISSN |
75 | 3 | 0925-1022 |
Citations | PageRank | References |
2 | 0.66 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gook Hwa Cho | 1 | 2 | 3.03 |
| Namhun Koo | 2 | 3 | 5.76 |
| Eunhye Ha | 3 | 2 | 1.00 |
| Soonhak Kwon | 4 | 170 | 22.00 |