Finite field towers: Iterated presentation and complexity of arithmetic. (English) Zbl 1037.11088
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.
Reviewer: Wilfried Meidl (Singapore)
MSC:
| 11T30 | Structure theory for finite fields and commutative rings (number-theoretic aspects) |
| 11Y16 | Number-theoretic algorithms; complexity |
| 68Q25 | Analysis of algorithms and problem complexity |
| 11T06 | Polynomials over finite fields |
References:
| [1] | V. B. Afanassiev, On the complexity of finite field arithmetic, in; V. B. Afanassiev, On the complexity of finite field arithmetic, in |
| [2] | V. B. Afanassiev, On the complexity of FFT over finite field, in; V. B. Afanassiev, On the complexity of FFT over finite field, in |
| [3] | V. B. Afanassiev and A. A. Davydov, On inversion in extended finite fields, in; V. B. Afanassiev and A. A. Davydov, On inversion in extended finite fields, in |
| [4] | V. B. Afanassiev and A. A. Davydov, On the binary complexity of arithmetic of the finite field tower, in; V. B. Afanassiev and A. A. Davydov, On the binary complexity of arithmetic of the finite field tower, in |
| [5] | V. B. Afanassiev and A. A. Davydov, Iterated presentation and complexity of arithmetic for tower of extended fields \(GF q^{p_∞}pq in \); V. B. Afanassiev and A. A. Davydov, Iterated presentation and complexity of arithmetic for tower of extended fields \(GF q^{p_∞}pq in \) · Zbl 0948.11047 |
| [6] | V. B. Afanassiev and A. A. Davydov, Design and arithmetic complexity of finite field towers \(GF p^{ mp_∞ \) · Zbl 0948.11046 |
| [7] | Aho, A. A.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1976), Addison-Wesley: Addison-Wesley Reading |
| [8] | Albert, A. A., Fundamental Concepts of Higher Algebra (1956), Univ. of Chicago Press: Univ. of Chicago Press Chicago · Zbl 0073.00802 |
| [9] | Blahut, R. E., Fast Algorithms for Digital Signal Processing (1985), Addison-Wesley: Addison-Wesley Reading · Zbl 0579.94001 |
| [10] | Brawley, J. V.; Schnibben, G. E., Infinite Algebraic Extensions of Finite Fields (1989), Amer. Math. Soc: Amer. Math. Soc Providence · Zbl 0674.12009 |
| [11] | Cohen, S. D., The explicit construction of irreducible polynomials over finite fields, Des. Codes Cryptogr., 2, 169-174 (1992) · Zbl 0768.11048 |
| [12] | J. L. Fan, and, C. Paar, On efficient inversion in tower fields of characteristic two, in; J. L. Fan, and, C. Paar, On efficient inversion in tower fields of characteristic two, in |
| [13] | Jungnickel, D., Finite Fields: Structure and Arithmetics (1992), Wissenchaftsverlag: Wissenchaftsverlag Mannheim |
| [14] | Lidl, R.; Niederreiter, H., Finite Fields (1983), Addison-Wesley: Addison-Wesley Reading · Zbl 0554.12010 |
| [15] | Preparata, F. P.; Sarwate, D. W., Computational complexity of Fourier transforms over finite fields, Math. Comp., 31, 740-751 (1977) · Zbl 0365.68053 |
| [16] | Schönhage, A.; Strassen, V., Schnelle Multiplikation grosser Zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007 |
| [17] | Shparlinski, I., Computational and Algorithmic Problems in Finite Fields (1992), Kluwer Academic: Kluwer Academic Dordrecht · Zbl 0780.11064 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
