More Web Proxy on the site http://driver.im/

research-article

Factoring Polynomials over Special Finite Fields

Authors:

Joachim von zur Gathen,

Hendrik W. LenstraAuthors Info & Claims

Finite Fields and Their Applications, Volume 7, Issue 1

Pages 5 - 28

https://doi.org/10.1006/ffta.2000.0306

Published: 01 January 2001 Publication History

Abstract

We exhibit a deterministic algorithm for factoring polynomials in one variable over finite fields. It is efficient only if a positive integer k is known for which k(p) is built up from small prime factors; here k denotes the kth cyclotomic polynomial, and p is the characteristic of the field. In the case k=1, when k(p)=p 1, such an algorithm was known, and its analysis required the generalized Riemann hypothesis. Our algorithm depends on a similar, but weaker, assumption; specifically, the algorithm requires the availability of an irreducible polynomial of degree r over Z/pZ for each prime number r for which k(p) has a prime factor l with l 1 mod r. An auxiliary procedure is devoted to the construction of roots of unity by means of Gauss sums. We do not claim that our algorithm has any practical value.

References

[1]

L. M. Adleman and H. W. Lenstra, Jr., Finding irreducible polynomials over finite fields, inProceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), Berkeley, 1986, pp. 350-355.

[2]

The orders of the linear groups. Comm. Pure Appl. Math. v8. 355-365.

[3]

. 1969. Addison¿Wesley, Reading.

[4]

Factoring with cyclotomic polynomials. Math. Comput. v52. 201-219.

[5]

. 1996. MIT Press, Cambridge.

[6]

Factoring polynomials over large finite fields. Math. Comput. v24. 713-735.

[7]

Factorization of polynomials over finite fields in subexponential time under GRH. In: Adleman, L.M., Huang, M.-D. (Eds.), Algorithmic Number Theory (ANTS-I), 877. Springer¿Verlag, Berlin. pp. 209-219.

[8]

Factoring polynomials and primitive elements for special primes. Theoret. Comput. Sci. v52. 77-89.

[9]

Generalized Riemann hypothesis and factoring polynomials over finite fields. J. Algorithms. v12. 464-481.

[10]

. 1993. Addison¿Wesley, Reading.

[11]

Algorithms in algebraic number theory. Bull. Amer. Math. Soc. v26. 211-244.

[12]

Finding isomorphisms between finite fields. Math. Comput. v56. 329-347.

[13]

The relationship between breaking the Diffie¿Hellman protocol and computing discrete logarithms. SIAM J. Comput. v28. 1689-1721.

[14]

Calcul déterministe des racines d'un polynôme dans un corps fini. C. R. Acad. Sci. Paris Sér. I Math. v306. 467-472.

[15]

Counting the numbers factorable via cyclotomic methods. J. Algorithms. v19. 250-265.

[16]

Factoring polynomials modulo special primes. Combinatorica. v9. 199-206.

[17]

Elliptic curves over finite fields and the computation of square roots mod p. Math. Comput. v44. 483-494.

[18]

New algorithms for finding irreducible polynomials over finite fields. Math. Comput. v54. 435-447.

Cited By

Grześkowiak M(2019)Algorithms for Relatively Cyclotomic PrimesFundamenta Informaticae10.5555/2594934.2594938125:2(161-181)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/2594934.2594938
Bhargava VIvanyos GMittal RSaxena NYap CEl Din M(2017)Irreducibility and Deterministic r-th Root Finding over Finite FieldsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087620(37-44)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087620
Ivanyos GKarpinski MSaxena NJohnson JPark HKaltofen E(2009)Schemes for deterministic polynomial factoringProceedings of the 2009 international symposium on Symbolic and algebraic computation10.1145/1576702.1576730(191-198)Online publication date: 28-Jul-2009
https://dl.acm.org/doi/10.1145/1576702.1576730
Show More Cited By

Recommendations

Galois groups and factoring polynomials over finite fields
SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science

Let p be a prime and F be a polynomial with integer coefficients. Suppose that the discriminant of F is not divisible by p, and denote by m the degree of the splitting field of F over Q and by L the maximal size of the coefficients of F. Then, assuming ...
Reversed Dickson polynomials over finite fields

Reversed Dickson polynomials over finite fields are obtained from Dickson polynomials D"n(x,a) over finite fields by reversing the roles of the indeterminate x and the parameter a. We study reversed Dickson polynomials with emphasis on their ...
Irreducible polynomials over finite fields with prescribed trace/prescribed constant term

We obtain an equivalent version of Carlitz's formula for the number of monic irreducible polynomials of degree n and trace @c<>0 over a finite field via an integer recurrence. Similar expressions for the @c=0 case are also given. We also obtain formulas ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Finite Fields and Their Applications

Finite Fields and Their Applications Volume 7, Issue 1

January, 2001

252 pages

ISSN:1071-5797

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 January 2001

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Grześkowiak M(2019)Algorithms for Relatively Cyclotomic PrimesFundamenta Informaticae10.5555/2594934.2594938125:2(161-181)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/2594934.2594938
Bhargava VIvanyos GMittal RSaxena NYap CEl Din M(2017)Irreducibility and Deterministic r-th Root Finding over Finite FieldsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087620(37-44)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087620
Ivanyos GKarpinski MSaxena NJohnson JPark HKaltofen E(2009)Schemes for deterministic polynomial factoringProceedings of the 2009 international symposium on Symbolic and algebraic computation10.1145/1576702.1576730(191-198)Online publication date: 28-Jul-2009
https://dl.acm.org/doi/10.1145/1576702.1576730
Maurer URaub D(2007)Black-box extension fields and the inexistence of field-homomorphic one-way permutationsProceedings of the Advances in Crypotology 13th international conference on Theory and application of cryptology and information security10.5555/1781454.1781490(427-443)Online publication date: 2-Dec-2007
https://dl.acm.org/doi/10.5555/1781454.1781490
van de Woestijne CGao XLabahn G(2005)Deterministic equation solving over finite fieldsProceedings of the 2005 international symposium on Symbolic and algebraic computation10.1145/1073884.1073932(348-353)Online publication date: 24-Jul-2005
https://dl.acm.org/doi/10.1145/1073884.1073932

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents