Article

Free access

Factoring polynomials over large finite fields*

Author:

E. R. BerlekampAuthors Info & Claims

SYMSAC '71: Proceedings of the second ACM symposium on Symbolic and algebraic manipulation

Page 223

https://doi.org/10.1145/800204.806290

Published: 23 March 1971 Publication History

PDF eReader

Abstract

This paper reviews some of the known algorithms for factoring polynomials over finite fields and presents a new deterministic procedure for reducing the problem of factoring an arbitrary polynomial over the Galois field GF(p ^m) to the problem of finding the roots in GF(p) of certain other polynomials over GF(p). The amount of computation and the storage space required by these algorithms are algebraic in both the degree of the polynomial to be factored and the logarithm of the order of the finite field.

Certain observations on the application of these methods to the factorization of polynomials over the rational integers are also included.

Cited By

View all

Lu GZhandry M(2024)Limits on the Power of Prime-Order Groups: Separating Q-Type from Static AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68388-6_3(46-74)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68388-6_3
Repka MCayrel P(2014)Cryptography Based on Error Correcting CodesMultidisciplinary Perspectives in Cryptology and Information Security10.4018/978-1-4666-5808-0.ch005(133-156)Online publication date: 2014
https://doi.org/10.4018/978-1-4666-5808-0.ch005
Canetti RPaneth OPapadopoulos DTriandopoulos N(2014)Verifiable Set Operations over Outsourced DatabasesProceedings of the 17th International Conference on Public-Key Cryptography --- PKC 2014 - Volume 838310.1007/978-3-642-54631-0_7(113-130)Online publication date: 26-Mar-2014
https://dl.acm.org/doi/10.1007/978-3-642-54631-0_7
Show More Cited By

Index Terms

Factoring polynomials over large finite fields*
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations in finite fields
      2. Number-theoretic computations

Recommendations

Factoring Polynomials over Special Finite Fields

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, ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SYMSAC '71: Proceedings of the second ACM symposium on Symbolic and algebraic manipulation

March 1971

464 pages

ISBN:9781450377867

DOI:10.1145/800204

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 March 1971

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
127
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)7

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lu GZhandry M(2024)Limits on the Power of Prime-Order Groups: Separating Q-Type from Static AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68388-6_3(46-74)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68388-6_3
Repka MCayrel P(2014)Cryptography Based on Error Correcting CodesMultidisciplinary Perspectives in Cryptology and Information Security10.4018/978-1-4666-5808-0.ch005(133-156)Online publication date: 2014
https://doi.org/10.4018/978-1-4666-5808-0.ch005
Canetti RPaneth OPapadopoulos DTriandopoulos N(2014)Verifiable Set Operations over Outsourced DatabasesProceedings of the 17th International Conference on Public-Key Cryptography --- PKC 2014 - Volume 838310.1007/978-3-642-54631-0_7(113-130)Online publication date: 26-Mar-2014
https://dl.acm.org/doi/10.1007/978-3-642-54631-0_7
Erotokritou SDesmedt Y(2012)Human perfectly secure message transmission protocols and their applicationsProceedings of the 8th international conference on Security and Cryptography for Networks10.1007/978-3-642-32928-9_30(540-558)Online publication date: 5-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-32928-9_30
Chakrabarti SChandrasekhar SSinghal MCalvert K(2009)An Efficient and Scalable Quasi-Aggregate Signature Scheme Based on LFSR SequencesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2008.26120:7(1059-1072)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1109/TPDS.2008.261
Moses JSammet JTobey RMoses J(1971)Symbolic integration the stormy decadeProceedings of the second ACM symposium on Symbolic and algebraic manipulation10.1145/800204.806313(427-440)Online publication date: 23-Mar-1971
https://dl.acm.org/doi/10.1145/800204.806313
Moses J(1971)Symbolic integrationCommunications of the ACM10.1145/362637.36265114:8(548-560)Online publication date: 1-Aug-1971
https://dl.acm.org/doi/10.1145/362637.362651

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Factoring Polynomials over Special Finite Fields

Galois groups and factoring polynomials over finite fields

Reversed Dickson polynomials over finite fields