zbMATH — the first resource for mathematics

Fast construction of irreducible polynomials over finite fields. (English) Zbl 1287.11141
Summary: We present a randomized algorithm that on inputting a finite field \(\mathbf K\) with \(q\) elements and a positive integer \(d\) outputs a degree \(d\) irreducible polynomial in \(\mathbf K[x]\). The running time is \(d^{1+\varepsilon(d)}\times(\log q)^{5+\varepsilon(q)}\) elementary operations. The function \(\varepsilon\) in this expression is a real positive function belonging to the class \(o(1)\), especially, the complexity is quasi-linear in the degree \(d\). Once given such an irreducible polynomial of degree \(d\), we can compute random irreducible polynomials of degree \(d\) at the expense of \(d^{1+\varepsilon(d)} \times (\log q)^{1+\varepsilon(q)}\) elementary operations only.

11Y16 Number-theoretic algorithms; complexity
11T06 Polynomials over finite fields
12E05 Polynomials in general fields (irreducibility, etc.)
68Q25 Analysis of algorithms and problem complexity
68W20 Randomized algorithms
68W30 Symbolic computation and algebraic computation
Full Text: DOI arXiv
[1] L.M. Adleman and H. W. Lenstra, Jr., Finding irreducible polynomials over finite fields, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, ACM, Boston, MA, 1983, pp. 350–355.
[2] M. Ben-Or, Probabilistic algorithms in finite fields, 22nd Annual Symposium on Foundations of Computer Science 11 (1981), 394–398. · doi:10.1109/SFCS.1981.37
[3] A. Bostan, Ph. Flajolet, B. Salvy and É. Schost, Fast computation of special resultants, Journal of Symbolic Computation 41 (2006), 1–29. · Zbl 1121.13037 · doi:10.1016/j.jsc.2005.07.001
[4] A. Bostan, L. González-Vega, H. Perdry and É. Schost, From Newton sums to coefficients: complexity issues in characteristic p, Proceedings of MEGA’05, 2005.
[5] J. von zur Gathen and J. Gerhard, Modern Computer Algebra, second edition, Cambridge University Press, 2003. · Zbl 1055.68168
[6] J. Giraud, Remarque sur une formule de Shimura-Taniyama, Inventiones Mathematicae 5 (1968), 231–236. · Zbl 0165.54801 · doi:10.1007/BF01425552
[7] E. W. Howe, On the group orders of elliptic curves over finite fields, Compositio Mathematica 85 (1993), 229–247. · Zbl 0793.14023
[8] H. Iwaniec, On the problem of Jacobsthal, Demonstratio Mathematica 11 (1978), 225–231. · Zbl 0378.10029
[9] E. Kaltofen and V. Y. Pan, Parallel solution of Toeplitz and Toeplitz-like linear systems over fields of small positive characteristic, in Proceedings of PASCO’94, Lecture Notes Series on Computing 5, World Scientific Publishing Company, Singapore, 1994, pp. 225–233.
[10] K. S. Kedlaya and C. Umans, Fast modular composition in any characteristic, in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2008, pp. 146–155.
[11] H. W. Lenstra, Jr., Factoring integers with elliptic curves, Annals of Mathematics 126 (1987), 649–673. · Zbl 0629.10006 · doi:10.2307/1971363
[12] H. W. Lenstra, Jr., Algorithms for finite fields, in Number Theory and Cryptography (Sydney, 1989), London Mathematical Society Lecture Note Series 154, Cambridge University Press, 1990, pp. 76–85.
[13] H. W. Lenstra, Jr., Finding isomorphisms between finite fields, Mathematics of Computation, Vol. 56, 193 (1991), 329–347. · Zbl 0709.11072
[14] H. W. Lenstra, Jr., Complex multiplication structure of elliptic curves, Journal of Number Theory 56 (1996), 227–241. · Zbl 1044.11590 · doi:10.1006/jnth.1996.0015
[15] H. W. Lenstra, Jr. and B. de Smit, Standard models for finite fields: the definition, http://www.math.leidenuniv.nl/\(\sim\)desmit , 2008, pp. 1–4.
[16] R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Cambridge, MA, 1983.
[17] Q. Liu, Algebraic Geometry and Arithmetic Curves, Oxford Graduate Texts in Mathematics 6, Oxford University Press, 2002. · Zbl 0996.14005
[18] D. Panario and B. Richmond, Analysis of Ben-Or’s polynomial irreducibility test, Random Structures and Algorithms 13 (1998), 439–456. · Zbl 0960.11052 · doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<439::AID-RSA13>3.0.CO;2-U
[19] C. H. Papadimitriou, Computational Complexity, Addison Wesley, Cambridge, MA, 1967. · Zbl 0557.68033
[20] A. Schönhage, Fast parallel computation of characteristic polynomials by Leverrier’s power sum method adapted to fields of finite characteristic, in Automata, Languages and Programming (Lund, 1993), Lecture Notes in Computer Science 700, 1993, Springer, Berlin, pp. 410–417.
[21] J.-P. Serre, Complex multiplication, in Algebraic Number Theory (J. W. S. Cassels and A. Fröhlich eds.), Academic Press, New York, 1967.
[22] V. Shoup, Fast construction of irreducible polynomials over finite fields, in Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (Austin, TX, 1993), ACM, New York, 1993, pp. 484–492. · Zbl 0820.11078
[23] J. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106, Springer-Verlag, Berlin, 1986; expanded 2nd edition, 2009. · Zbl 0585.14026
[24] C. Umans, Fast polynomial factorization and modular composition in small characteristic, in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 1986, pp. 350–355.
[25] J. Vélu, Isogénies entre courbes elliptiques, Comptes Rendus de l’Académie des Sciences, Série I 273 (1971), 238–241.
[26] W. C. Waterhouse, Abelian varieties over finite fields, Annales Scientifiques de l’École Normale Supérieure, Série 4 2 (1969), 521–560. · Zbl 0188.53001
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.