Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.06.2015 | Ausgabe 3/2015

Designs, Codes and Cryptography 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

Weitere Artikel der Ausgabe 3/2015

Designs, Codes and Cryptography 3/2015 Zur Ausgabe

Premium Partner

    Bildnachweise