scroll identifier for mobile
main-content

## Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.06.2015 | Ausgabe 3/2015

# New cube root algorithm based on the third order linear recurrence relations in finite fields

Zeitschrift:
Designs, Codes and Cryptography > Ausgabe 3/2015
Autoren:
Gook Hwa Cho, Namhun Koo, Eunhye Ha, Soonhak Kwon
Wichtige Hinweise
Communicated by D. Panario.

## Abstract

In this paper, we present a new cube root algorithm in the finite field $$\mathbb {F}_{q}$$ with $$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}$$ with $$q \equiv 1 \pmod {9}$$, we show that there is an irreducible polynomial $$f(x)$$ with root $$\alpha \in \mathbb {F}_{q^{3}}$$ such that $$Tr\left( \alpha ^{\frac{q^{2}+q-2}{9}}\right)$$ is a cube root of $$c$$. Consequently we find an efficient cube root algorithm based on the third order linear recurrence sequences arising from $$f(x)$$. The complexity estimation shows that our algorithm is better than the previously proposed Cipolla–Lehmer type algorithms.

### Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Literatur
Über diesen Artikel

Zur Ausgabe