Some Remarks on Testing Irreducibility of Polynomials and Normality of Bases in Finite Fields

• Autorzy: Gashkov, S.B. , Gashko, I.B.
• Języki publikacji: EN

Abstrakty

EN

We prove some improvements for well-known upper bound of complexity of testing irreducibility of polynomials over finite fields. Also the fast modification of well-known probabilistic algorithm finding a normal bases in special finite fields is presented.

Słowa kluczowe

EN

finite fields; irreducible polynomials; normal base; addition chains

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 3
• Strony: 227-238
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Gashkov, S.B.

autor

Gashko, I.B.

• Department of Mechanics and Mathematics, Moscow State University, Vorobiovy Gory, Moscow, Russia,

Bibliografia

• [1] Blahut, R. E.: Fast Algorithms for Digital Signal Processing, Addison-Wesley, 1984.
• [2] Brent, R. P., Kung, H. T.: Fast algoritms for manipulating formal power series, Journal of the ACM, 25(4), 1978, 581-595.
• [3] Cantor, D.: On arithmetic algorithm over finite fields, Combinatorial theory, Series A 50, 1989, 285-300.
• [4] Cantor, D., Kaltofen E.: On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, 28, 1991, 693-701.
• [5] Gashkov, S. B.: Remarks on the fast multiplication of polynomials, and Fourier and Hartley transforms, Discrete Math. Appl., 10(5), 2000, 499-528.
• [6] Gashkov, S. B., Kochergin, V. V.: On addition chains of vectors, gate circuits, and the complexity of computation of power, Syberian Advances in Mathematics, 4(4), 1994, 1-16.
• [7] von zur Gathen, J., Gerhard, J.: Polynomial factorization over GF(2), Math. Computation, 71(240), 2002, 1677-1698.
• [8] von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, Cambridge University Press, 2003.
• [9] von zur Gathen, J., Giesbrecht, M.: Constructing normal bases in finite fields, Symbolic Computation, 10, 1990, 547-579.
• [10] von zur Gathen, J., Shoup, V.: Computing Frobeius maps and factoring of polynomials, Computational complexity, 2, 1992, 187-224.
• [11] Huang, X., Pan, V.: Fast rectangular matrix multiplication and applications, Journal of Complexity 14, 1998, 257-299.
• [12] Knut, D.: The Art of Programming, vol. II, Addison-Wesley Longman, 1998.
• [13] Lidl, R., Niderreiter, H.: Finite Fields, Addison-Wesley, 1983.
• [14] Prachar, K.: Primzahlverteilung, Springer-Verlag, 1957.
• [15] Schönhage A.: Schnelle berechnung von kettenbruchentwicklungen, Acta Informatica, 1, 1971, 139-144.
• [16] Schönhage A.: Schnelle multiplikation von polynomen ¨uber k¨orpern der charakteristik 2, Acta Informatica, 7, 1977, 395-398.
• [17] Shoup V.: Fast construction of irreducible polynomials over finite fields, Symbolic Computation, 17, 1994, 371-391.
• [18] Sierpiński W.: 200 Zadań z Elementarnej Teorii Liczb, Warszawa, 1964.