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

DOI10.1007/s10623-013-9910-8zbMath1361.11083OpenAlexW2085005354MaRDI QIDQ2345923

Eunhye Ha, Soonhak Kwon, Namhun Koo, Gook Hwa Cho

Publication date: 21 May 2015

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10623-013-9910-8

zbMATH Keywords

finite fieldlinear recurrence relationcube rootTonelli-Shanks algorithmCipolla-Lehmer algorithmAdleman-Manders-Miller algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06)

Related Items

On the Cipolla-Lehmer type algorithms in finite fields ⋮ Faster point compression for elliptic curves of $j$-invariant $0$ ⋮ A refinement of Müller's cube root algorithm ⋮ New point compression method for elliptic \(\mathbb{F}_{q^2}\)-curves of \(j\)-invariant 0 ⋮ Efficient computation of terms of linear recurrence sequences of any order ⋮ Unnamed Item ⋮ Indifferentiable hashing to ordinary elliptic \(\mathbb{F}_{q} \)-curves of \(j=0\) with the cost of one exponentiation in \(\mathbb{F}_{q} \)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved generalized Atkin algorithm for computing square roots in finite fields
• Formulas for cube roots in \(\mathbb F_{3^m}\)
• Efficient \(p\)th root computations in finite fields of characteristic \(p\)
• On the computation of square roots in finite fields
• Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers
• Efficient computation of roots in finite fields
• Structure computation and discrete logarithms in finite abelian $p$-groups
• A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
• Public-key cryptosystems based on cubic finite field extensions
• Improved Computation of Square Roots in Specific Finite Fields
• Low Complexity Cubing and Cube Root Computation over $\F_{3^m}$ in Polynomial Basis
• Advances in Cryptology - ASIACRYPT 2003

This page was built for publication: New cube root algorithm based on the third order linear recurrence relations in finite fields