Czasopismo
2010
|
Vol. 104, nr 3
|
227-238
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
227-238
Opis fizyczny
Bibliogr. 18 poz.
Twórcy
autor
autor
- Department of Mechanics and Mathematics, Moscow State University, Vorobiovy Gory, Moscow, Russia, gashkov@lsili.ru
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS8-0011-0029