Finite field towers: Iterated presentation and complexity of arithmetic.
type: Item
instance of: scholarly article
title: Finite field towers: Iterated presentation and complexity of arithmetic.
zbMATH Open document ID: 1037.11088
author: Valentine B. Afanassiev
author: Alexander A. Davydov
published in: Finite Fields and their Applications
publication date: 2002-08-15T00:00:00Z
review text: Let \(p_k\), \(k = 1, \ldots, t\), be prime divisors of \(q-1\) and \(q \equiv 1\bmod 4\) if \(2 \in \{p_1,\ldots, p_t\}\). Suppose that \(P = p_1^{n_1}p_2^{n_2}\cdots p_t^{n_t}\). It is shown that then the field \(\mathbb F_{q^P}\) can be represented as a tower of extensions of \(\mathbb F_q\) generated by irreducible binomials. Based on this fact a fast multiplication and a fast inversion algorithm in the field \(\mathbb F_{q^P}\) is established and the complexity of these algorithms is analyzed.
reviewed by: Wilfried Meidl
Mathematics Subject Classification ID: 11T30
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11T06
zbMATH DE Number: 1781829
zbMATH Keywords: finite field towers
zbMATH Keywords: fast multiplication
zbMATH Keywords: fast inversion
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: ffta.2001.0337
OpenAlex ID: W2347133766
cites work: Q4500969
cites work: Q4500970
cites work: Q3236675
cites work: Q3703780
cites work: Infinite Algebraic Extensions of Finite Fields
cites work: The explicit construction of irreducible polynomials over finite fields
cites work: Q3216750
cites work: Computational Complexity of Fourier Transforms Over Finite Fields
cites work: Fast multiplication of large numbers
cites work: Q3137899
DOI: 10.1006/FFTA.2001.0337
Recommended article: Q4664639
Recommended article: Q4500969
Recommended article: Q3499664
Recommended article: On tame towers over finite fields
Recommended article: Q4500970
Recommended article: Recursive Towers of Function Fields over Finite Fields
Recommended article: Finite Fields and Applications
Recommended article: Q5706766
Recommended article: On number fields towers defined by iteration of polynomials
Recommended article: Polynomial-time presentations of algebraic number fields
description: scientific article; zbMATH DE number 1781829