摘要: The main result of this paper a new algorithm for constructing an irreducible polynomial specified degree n over finite field Fq . is probabilistic, and asymptotically faster than previously known algorithms problem. It uses expected number O-(n2 + log q) operations in Fq, where the "soft-O" O- indicates implicit factor (log )O(1). In addition, two irreducibility tests are described.
acm.org
core.ac.uk
elsevier.com
sci-hub.se 参考文章(20)
J. A. Thiong Ly, Note for computing the minimum polynomial of elements in large finite fields Proceedings of the third international colloquium on Coding theory and applications. pp. 185- 192 ,(1988) , 10.1007/BFB0019856
Josep Rifà, Joan Borrell, Improving the Time Complexity of the Computation of Irreducible and Primitive Polynomials in Finite Fields Applicable Algebra in Engineering, Communication and Computing. pp. 352- 359 ,(1991) , 10.1007/3-540-54522-0_123
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
N. Alon, O. Goldreich, J. Hastad, R. Peralta, Simple construction of almost k-wise independent random variables foundations of computer science. ,vol. 2, pp. 544- 553 ,(1990) , 10.1109/FSCS.1990.89575
Walter Baur, Volker Strassen, The complexity of partial derivatives Theoretical Computer Science. ,vol. 22, pp. 317- 330 ,(1983) , 10.1016/0304-3975(83)90110-X
Don Coppersmith, Shmuel Winograd, Matrix multiplication via arithmetic progressions Journal of Symbolic Computation. ,vol. 9, pp. 251- 280 ,(1990) , 10.1016/S0747-7171(08)80013-2
Joachim von zur Gathen, Victor Shoup, Computing Frobenius maps and factoring polynomials Computational Complexity. ,vol. 2, pp. 187- 224 ,(1992) , 10.1007/BF01272074
Richard P Brent, Fred G Gustavson, David Y.Y Yun, Fast solution of toeplitz systems of equations and computation of Padé approximants Journal of Algorithms. ,vol. 1, pp. 259- 295 ,(1980) , 10.1016/0196-6774(80)90013-9
Michael O. Rabin, Probabilistic Algorithms in Finite Fields SIAM Journal on Computing. ,vol. 9, pp. 273- 280 ,(1980) , 10.1137/0209024
Michael Ben-Or, Probabilistic algorithms in finite fields 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981). pp. 394- 398 ,(1981) , 10.1109/SFCS.1981.37