on Factoring Polynomials Over Finite Fields: A Survey
---
paper_title: The Theory of Error-Correcting Codes

paper_content:

Linear Codes. Nonlinear Codes, Hadamard Matrices, Designs and the Golay Code. An Introduction to BCH Codes and Finite Fields. Finite Fields. Dual Codes and Their Weight Distribution. Codes, Designs and Perfect Codes. Cyclic Codes. Cyclic Codes: Idempotents and Mattson-Solomon Polynomials. BCH Codes. Reed-Solomon and Justesen Codes. MDS Codes. Alternant, Goppa and Other Generalized BCH Codes. Reed-Muller Codes. First-Order Reed-Muller Codes. Second-Order Reed-Muller, Kerdock and Preparata Codes. Quadratic-Residue Codes. Bounds on the Size of a Code. Methods for Combining Codes. Self-dual Codes and Invariant Theory. The Golay Codes. Association Schemes. Appendix A. Tables of the Best Codes Known. Appendix B. Finite Geometries. Bibliography. Index.
---
paper_title: Factoring univariate integral polynomial in polynomial average time

paper_content:

Let A be a primitive squarefree univariate integral polynomial of degree n. An irreducible factor of A can be found by forming products of lifted modulo p factors of A for a suitable small prime p. One can either form first the products consisting of the smallest numbers of lifted factors (cardinality procedure) or form first the products with smallest degrees (degree procedure). Let ∏ be the partition of n consisting of the degrees of the irreducible factors of A. The average number of products formed before finding an irreducible factor of A is a function of ∏, C(∏) or D(∏) respectively. Let C*(n) (D*(n)) be the maximum of C(∏) (D(∏)) for all partitions, ∏, of n. Subject to the validity of two conjectures, for which considerable evidence is presented, it is proved that C*(n) is dominated by n2 whereas D*(n) is exponential. If the conjectures are true then the cardinality procedure results in a complete factorization algorithm for primitive univariate integral polynomials whose average computing time, in a very strong sense, is dominated by a polynomial function of its degree n.
---
paper_title: On Hensel factorization, I

paper_content:

A p-adic method for the constructive factorization of monic polynomials over a dedekind ring o and the ideal theory of o[x] are developed.
---
paper_title: Factoring polynomials with rational coefficients

paper_content:

In this paper we present a polynomial-time algorithm to solve the following problem: given a non-zero polynomial fe Q(X) in one variable with rational coefficients, find the decomposition of f into irreducible factors in Q(X). It is well known that this is equivalent to factoring primitive polynomials feZ(X) into irreducible factors in Z(X). Here we call f~ Z(X) primitive if the greatest common divisor of its coefficients (the content of f) is 1. Our algorithm performs well in practice, cf. (8). Its running time, measured in bit operations, is O(nl2+n9(log(fD3).
---
paper_title: A knapsack-type public key cryptosystem based on arithmetic in finite fields

paper_content:

We introduce a new knapsack type public key cryptosystem. The system is based on a novel application of arithmetic in finite fields, following a construction by Bose and Chowla. Appropriately choosing the parameters, we can control the density of the resulting knapsack. In particular, the density can be made high enough to foil “low density” attacks against our system. At the moment, we do not know of any attacks capable of “breaking” this system in a reasonable amount of time.
---
paper_title: On the Chor—Rivest knapsack cryptosystem

paper_content:

Among all public-key cryptosystems that depend on the knapsack problem, the system proposed by Chor and Rivest (IEEE Trans. Inform. Theory 34 (1988), 901---909) is one of the few that have not been broken. The main difficulty in implementing their system is the computation of discrete logarithms in large finite fields. In this note we describe the "powerline system," which is a modification of the Chor-Rivest system that does not have this shortcoming. The powerline system, which is not a knapsack system, is at least as secure as the original Chor-Rivest system.
---
paper_title: A New Polynomial Factorization Algorithm and its Implementation

paper_content:

Abstract We consider the problem of factoring univariate polynomials over a finite field. We demonstrate that the new baby step/giant step factoring method , recently developed by Kaltofen and Shoup, can be made into a very practical algorithm. We describe an implementation of this algorithm, and present the results of empirical tests comparing this new algorithm with others. When factoring polynomials modulo large primes, the algorithm allows much larger polynomials to be factored using a reasonable amount of time and space than was previously possible. For example, this new software has been used to factor a "generic" polynomial of degree 2048 modulo a 2048-bit prime in under 12 days on a Sun SPARC-station 10, using 68 MB of main memory.
---
paper_title: Matrix multiplication via arithmetic progressions

paper_content:

We present a new method for accelerating matrix multiplication asymptotically. Thiswork builds on recent ideas of Volker Strassen, by using a basic trilinear form which is not a matrix product. We make novel use of the Salem-Spencer Theorem, which gives a fairly dense set of integers with no three-term arithmetic progression. Our resulting matrix exponent is 2.376.
---
paper_title: On arithmetical algorithms over finite fields

paper_content:

Abstract Standard methods for calculating over G F ( p n ), the finite field of p n elements, require an irreducible polynomial of degree n with coefficients in G F ( p ). Such a polynomial is usually obtained by choosing it randomly and then verifying that it is irreducible, using a probabilistic algorithm. If it is not, the procedure is repeated. Here we given an explicit basis, with multiplication table, for the fields G F ( p p k ), for k = 0, 1, 2,…, and their union. This leads to efficient computational methods, not requiring the preliminary calculation of irreducible polynomials over finite fields and, at the same time, yields a simple recursive formula for irreducible polynomials which generate the fields. The fast Fourier transform (FFT) is a method for efficiently evaluating (or interpolating) a polynomial of degree n at all of the n th roots of unity, i.e., on the finite multiplicate subgroups of F , in O ( n log n ) operations in the underlying field. We give an analogue of the fast Fourier transform which efficiently evaluates a polynomial on some of the additive subgroups of F . This yields new “fast” algorithms for polynomial computation.
---
paper_title: On square-free decomposition algorithms

paper_content:

In this paper, we will give three different (including revamped versions of Horowitz's and Musser's) algorithms for computing the SQFR decomposition of polynomials in R[x]. Some algorithm analysis will be carried out to show the (asymptotic) superiority of the algorithm we propose (last of the three).
---
paper_title: Subquadratic-time factoring of polynomials over finite fields

paper_content:

New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant cardinality in time O(n1.815). Previous algorithms required time Θ(n2+o(1)). The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree n over the finite field Fq with q elements, the algorithms use O(n1.815 log q) arithmetic operations in Fq . The new “baby step/giant step” techniques used in our algorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields.
---
paper_title: Factoring polynomials over large finite fields*

paper_content:

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.
---
paper_title: Computing Frobenius maps and factoring polynomials

paper_content:

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented whose asymptotic running time improves upon previous results. To factor a polynomial of degree n over F q , the algorithm uses O (( n 2 + n log q )•(log n ) 2 log log n ) arithmetic operations in F q . The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.
---
paper_title: Fast Rectangular Matrix Multiplication and Applications

paper_content:

First we study asymptotically fast algorithms for rectangular matrix multiplication. We begin with new algorithms for multiplication of ann?nmatrix by ann?n2matrix in arithmetic timeO(n?),?=3.333953?, which is less by 0.041 than the previous record 3.375477?. Then we present fast multiplication algorithms for matrix pairs of arbitrary dimensions, estimate the asymptotic running time as a function of the dimensions, and optimize the exponents of the complexity estimates. For a large class of input matrix pairs, we improve the known exponents. Finally we show three applications of our results: (a)we decrease from 2.851 to 2.837 the known exponent of the work bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of ann?nmatrix, as well as for the solution to a nonsingular linear system ofnequations, (b)we asymptotically accelerate the known sequential algorithms for the univariate polynomial composition modxn, yielding the complexity boundO(n1.667) versus the old record ofO(n1.688), and for the univariate polynomial factorization over a finite field, and (c)we improve slightly the known complexity estimates for computing basic solutions to the linear programming problem withmconstraints andnvariables.
---
paper_title: A New Polynomial Factorization Algorithm and its Implementation

paper_content:

Abstract We consider the problem of factoring univariate polynomials over a finite field. We demonstrate that the new baby step/giant step factoring method , recently developed by Kaltofen and Shoup, can be made into a very practical algorithm. We describe an implementation of this algorithm, and present the results of empirical tests comparing this new algorithm with others. When factoring polynomials modulo large primes, the algorithm allows much larger polynomials to be factored using a reasonable amount of time and space than was previously possible. For example, this new software has been used to factor a "generic" polynomial of degree 2048 modulo a 2048-bit prime in under 12 days on a Sun SPARC-station 10, using 68 MB of main memory.
---
paper_title: A new algorithm for factoring polynomials over finite fields

paper_content:

in F[t]. There are two standard methods; one is due to E. Berlekamp, the other appears to be a "folk method". Both are described by D. Knuth in [3, pp. 381-397]. Further improvements, for special values of q, are given by R. Moenck in [5J. See also E. Berlekamp [1]. (Note that both methods as described in the references apply only when d = 1, however, straightforward modifications, described below, allow d > 1.) Both methods use the calculation of resultants (or equivalently the solution of linear equations) to reduce the problem to finding the roots of a polynomial which has all of its roots in F. When p is very small, probabilistic methods are used. An improvement to the "folk method" method, along with a more explicit calculation of the work required, has recently been given by M. Rabin [6]. We present here a new probabilistic method which, when combined with the above algorithms, avoids the need for both resultants and linear equations. It leads to algorithms which are conceptually simpler than previous methods. Moreover, it works equally well for all finite fields F, regardless of the magnitude of q. When used for factoring a quadratic x2 a, it reduces to Berlekamp's algorithm. Other standard algorithms for factoring quadratics are due to D. H. Lehmer [4] and D. Shanks [7]. Our algorithm is also suitable for finding solutions of polynomial equations over finite fields.
---
paper_title: Computing Frobenius maps and factoring polynomials

paper_content:

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented whose asymptotic running time improves upon previous results. To factor a polynomial of degree n over F q , the algorithm uses O (( n 2 + n log q )•(log n ) 2 log log n ) arithmetic operations in F q . The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.
---
paper_title: Fast polynomial factorization over high algebraic extensions of finite fields

paper_content:

New algorithms are presented for factoring polynomials of degree n over the finite field of q elements, where q is a power of a fixed prime number. When log q = n, where a > 0 is constant, these algorithms are asymptotically faster than previous known algorithms, the fastest of which required time Ω(n(log q)), or Ω(n) in this case, which corresponds to the cost of computing x modulo an n degree polynomial. The new algorithms factor an arbitrary polynomial in time O(n+n). All measures are in fixed precision operations, that is in bit complexity. Moreover, in the special case where all the irreducible factors have the same degree, the new algorithms run in time O(n). In particular, one may test a polynomial for irreducibility in O(n) bit operations. These results generalize to the case where q = p, where p is a small prime number relative to q.
---
paper_title: A new algorithm for factoring polynomials over finite fields

paper_content:

in F[t]. There are two standard methods; one is due to E. Berlekamp, the other appears to be a "folk method". Both are described by D. Knuth in [3, pp. 381-397]. Further improvements, for special values of q, are given by R. Moenck in [5J. See also E. Berlekamp [1]. (Note that both methods as described in the references apply only when d = 1, however, straightforward modifications, described below, allow d > 1.) Both methods use the calculation of resultants (or equivalently the solution of linear equations) to reduce the problem to finding the roots of a polynomial which has all of its roots in F. When p is very small, probabilistic methods are used. An improvement to the "folk method" method, along with a more explicit calculation of the work required, has recently been given by M. Rabin [6]. We present here a new probabilistic method which, when combined with the above algorithms, avoids the need for both resultants and linear equations. It leads to algorithms which are conceptually simpler than previous methods. Moreover, it works equally well for all finite fields F, regardless of the magnitude of q. When used for factoring a quadratic x2 a, it reduces to Berlekamp's algorithm. Other standard algorithms for factoring quadratics are due to D. H. Lehmer [4] and D. Shanks [7]. Our algorithm is also suitable for finding solutions of polynomial equations over finite fields.
---
paper_title: Connections between the Algorithms of Berlekamp and Niederreiter for factoring Polynomials over

paper_content:

Abstract In this paper we determine an explicit isomorphism between the solution spaces of Berlekamp's and Niederreiter's algorithm for factoring polynomials over finite fields. This can be used for the implementation of a procedure combining the benefits of both methods.
---
paper_title: Factoring polynomials over large finite fields*

paper_content:

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.
---
paper_title: Tests and Constructions of Irreducible Polynomials over Finite Fields

paper_content:

In this paper we focus on tests and constructions of irreducible polynomials over finite fields. We revisit Rabin’s (1980) algorithm providing a variant of it that improves Rabin’s cost estimate by a log n factor. We give a precise analysis of the probability that a random polynomial of degree n contains no irreducible factors of degree less than O(log n). This probability is naturally related to Ben-Or’s (1981) algorithm for testing irreducibility of polynomials over finite fields. We also compute the probability of a polynomial being irreducible when it has no irreducible factors of low degree. This probability is useful in the analysis of various algorithms for factoring polynomials over finite fields. We present an experimental comparison of these irreducibility methods when testing random polynomials.
---
paper_title: Fast construction of irreducible polynomials over finite fields

paper_content:

The main result of this paper a new algorithm for constructing an irreducible polynomial of specified degree n over a finite field Fq . The algorithm is probabilistic, and is asymptotically faster than previously known algorithms for this problem. It uses an expected number of O-(n2 + n log q) operations in Fq, where the "soft-O" O- indicates an implicit factor of (log n )O(1). In addition, two new polynomial irreducibility tests are described.
---
paper_title: Univariate polynomial factorization over finite fields

paper_content:

Abstract This paper is a tutorial introduction to univariate polynomial factorization over finite fields. We recall the classical methods that induced most factorization algorithms (Berlekamp's and the Cantor-Zassenhaus ones) and some refinements which can be applied to these methods. Explicit algorithms are presented in a form suitable for almost immediate implementation. We give a detailed description of an efficient implementation of the Cantor-Zassenhaus algorithm used in the release 2 of the Axiom computer algebra system.
---
paper_title: Factoring polynomials over large finite fields*

paper_content:

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.
---
paper_title: Factoring Polynomials Using Fewer Random Bits

paper_content:

Let F be a field of q=p^n elements, where p is prime. We present two new probabilisticalgorithms for factoring polynomials in F[X] that make particularly efficient use of random bits. They are easy to implement, and require no randomness beyond an initial seed whose length is proportional to the input size. The first algorithm is based on a procedure of Berlekamp; on input f in F[X] of degree d, it uses d log"2p random bits and produces in polynomial time a complete factorisation of f with a failure probability of no more than 1/p^(^1^-^e^)^d^/^2. (Here @e denotes a fixed parameter between 0 and 1 that can be chosen by the implementer.) The second algorithm is based on a method of Cantor and Zassenhaus; it uses d log"2q random bits and fails to find a complete factorisation with probability no more than 1/q^(^1^-^e^)^d^/^4. For both of these algorithms, the failure probability is exponentially small in the number of random bits used.
---
paper_title: Computing Frobenius maps and factoring polynomials

paper_content:

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented whose asymptotic running time improves upon previous results. To factor a polynomial of degree n over F q , the algorithm uses O (( n 2 + n log q )•(log n ) 2 log log n ) arithmetic operations in F q . The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.
---
paper_title: A new algorithm for factoring polynomials over finite fields

paper_content:

in F[t]. There are two standard methods; one is due to E. Berlekamp, the other appears to be a "folk method". Both are described by D. Knuth in [3, pp. 381-397]. Further improvements, for special values of q, are given by R. Moenck in [5J. See also E. Berlekamp [1]. (Note that both methods as described in the references apply only when d = 1, however, straightforward modifications, described below, allow d > 1.) Both methods use the calculation of resultants (or equivalently the solution of linear equations) to reduce the problem to finding the roots of a polynomial which has all of its roots in F. When p is very small, probabilistic methods are used. An improvement to the "folk method" method, along with a more explicit calculation of the work required, has recently been given by M. Rabin [6]. We present here a new probabilistic method which, when combined with the above algorithms, avoids the need for both resultants and linear equations. It leads to algorithms which are conceptually simpler than previous methods. Moreover, it works equally well for all finite fields F, regardless of the magnitude of q. When used for factoring a quadratic x2 a, it reduces to Berlekamp's algorithm. Other standard algorithms for factoring quadratics are due to D. H. Lehmer [4] and D. Shanks [7]. Our algorithm is also suitable for finding solutions of polynomial equations over finite fields.
---
paper_title: Improving an algorithm for factoring polynomials over a finite field and constructing large irreducible polynomials

paper_content:

Let f(x)\in {\bf F}_{q}[X] be a polynomial with simple roots to be factored. The so-called Berlekamp subalgebra B spanned over {\bf F}_{q} by the idempotents of A={\bf F}_{q}[X]/(f(X)) is considered. An exponential technique introduced earlier is based upon taking elements from B at random and enables us to obtain idempotents and, from that, the factors of f(X). This algorithm is speeded up in three ways. The concept of a separating subset of B is introduced and the McEliece operator mapping A onto B is used to construct a small separating set. {\em Factoring} subsets of {\bf F}_{q} were defined and investigated previously. The algorithm and these subsets are used together with a process introduced by F. J. McWilliams for the rapid construction of primitive idempotents. Finally, an algorithm is introduced for constructing irreducible polynomials of {\bf F}_{q}[X] of degree d , for large values of d , in which the most expensive operation is the Euclidian algorithm applied to two polynomials of degree 2d .
---
paper_title: A Fast Monte-Carlo Test for Primality

paper_content:

Let n be an odd integer. Take a random number a from a uniform distribution on the set $\{1, 2,\cdots, n -1\}$. If a and n are relatively prime, compute the residue $\varepsilon \equiv a^{(n - 1)/2...
---
paper_title: A Deterministic Algorithm for Factorizing Polynomials over Extensions GF(p m ) of GF(p), p a Small Prime

paper_content:

Abstract A deterministic algorithm to factorize polynomials in GF(pm )[X] into irreducible factors over GF(pm ) (p prime, m>1) is proposed. The main idea is the use of two trace functions to define a new set of factorizing polynomials. The method appears efficient when p is a small prime; the degree m of extension may be large.
---
paper_title: Factorization of polynominals over finite fields in subexponential time under GRH

paper_content:

We show assuming the Generalized Riemann Hypothethis that the factorization of a one-variable polynomial of degree n over an explicitly given finite field of cardinality q can be done in deterministic time (nlog n log q)O(1). Since we need the hypothesis only to take roots in finite fields in polynomial time, the result can also be formulated in the following way: a polynomial equation over a finite field can be solved “by radicals” in subexponential time.
---
paper_title: Factoring Polynomials Over Finite Fields

paper_content:

Abstract We propose a new deterministic method of factoring polynomials over finite fields. Assuming the generalized Riemann hypothesis (GRH), we obtain, in polynomial time, the factorization of any polynomial with a bounded number of irreducible factors. Other consequences include a polynomial time algorithm to find a nontrivial factor of any completely splitting even-degree polynomial when a quadratic nonresidue in the field is given.
---
paper_title: On the Deterministic Complexity of Factoring Polynomials over Finite Fields

paper_content:

We present a new deterministic algorithm for factoring polynomials over Zp of degree n. We show that the worst-case running time of our algorithm is O(p12(log p)2n2+∈), which is faster than the running times of previous determi nistic algorithms with respect to both n and p. We also show that our algorithm runs in polynomial time for all but at most an exponentially small fraction of the polynomials of degree n over Zp. Specifically, we prove that the fraction of polynomials of degree n over Zp for which our algorithm fails to halt in time O((log p)2n2+∈) is ((n log p)2/p). Consequently, the average-case running time of our algorithm is polynomial in n and log p.
---
paper_title: Factoring polynomials modulo special primes

paper_content:

We consider the problem of factoring polynomials overGF(p) for those prime numbersp for which all prime factors ofp− 1 are small. We show that if we have a primitivet-th root of unity for every primet dividingp− 1 then factoring polynomials overGF(p) can be done in deterministic polynomial time.
---
paper_title: A Deterministic Algorithm for Factorizing Polynomials of Fq [X]

paper_content:

The general problem under consideration is actually solved for every semi-simple, commutative algebra A of finite dimension over a finite field F q . A probabilistic algorithm for decomposing an idempotent u of A into a sum of primitive idempotents was introduced in [1] and [2]. Here the probabilistic algorithm gives place to a deterministic one which, in particular, allows the factorization of polynomials of F q , [ X ].
---
paper_title: Galois Groups and Factoring Polynomials over Finite Fields

paper_content:

Let p be a prime and F be a polynomial with integer coefficients. Suppose that the discriminant of F is not divisible by p. 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 the generalized Riemann hypothesis (GRH ), the irreducible factors of F modulo p in (deterministic) time polynomial in deg F, m, L, and $\log p$ can be found. This is a generalization of a result of Huang [Riemann hypothesis and finding roots over finite fields, in Proceedings of the 17th ACM Symposium on Theory of Computing, Providence, Rhode Island, 1985, pp.121–130]. As an application, under GRH certain equations of the form $nP = R$ can be solved, where R is a given and P is an unknown point of an elliptic curve defined over $GF ( p )$ in polynomial time (n is counted in unary). Finally, an elliptic analogue of a result obtained recently by von zur Gathen [Theoretical Computer Science, 52 (1987), pp. 77–89] and independently by Mignotte and Schnorr [Compte...
---
paper_title: Elliptic curves over finite fields and the computation of square roots mod $p$

paper_content:

In this paper we present a deterministic algorithm to compute the number of F^-points of an elliptic curve that is defined over a finite field Fv and which is given by a Weierstrass equation. The algorithm takes 0(log9 q) elementary operations. As an application wc give an algorithm to compute square roots mod p. For fixed .i e Z, it takes 0(log9p) elementary operations to compute fx mod p. 1. Introduction. In this paper we present an algorithm to compute the number of F(/-points of an elliptic curve defined over a finite field F , which is given by a Weierstrass equation. We restrict ourselves to the case where the characteristic of F^ is not 2 or 3. The algorithm is deterministic, does not depend on any unproved hypotheses and takes 0(log9 0. If one applies fast multiplication techniques, the algorithm will take 0((|x|1/2log p)6+f) elementary operations for any e > 0. Let £ be an elliptic curve defined over the prime field Fp and let an affine model of it be given by a Weierstrass equation Y2 = X3 + AX + B (A,BeFp). An explicit formula for the number of F^-points on £ is given by
---
paper_title: On the efficiency of algorithms for polynomial factoring

paper_content:

Algorithms for factoring polynomials over finite fields are discussed. A construction is shown which reduces the final step of Berlekamp's algorithm to the problem of finding the roots of a polynomial in a finite field Zp. It is shown that if the characteristic of the field is of the form p = L 21 + 1, where I L, then the roots of a polynomial of degree n may be found in O(n log p + n log2 p) steps. As a result, a modification of Berlekamp's method can be performed in O(n + n log p + n log p) steps. If n is very large then an alternative method finds the factors of the polynomial in O(n2log n + n lognlogp). Some consequences and empirical evidence are discussed.
---
paper_title: Some Computational Aspects of Root Finding in GF(qm)

paper_content:

This paper is an implementation report comparing several variations of a deterministic algorithm for finding roots of polynomials in finite extension fields. Running times for problem instances in fields GF(2m), including m>1000, are given. Comparisons are made between the variations, and improvements achieved in running times are discussed.
---
paper_title: Subgroup refinement algorithms for root finding in GF(q)

paper_content:

This paper presents a generalization of Moenck’s root finding algorithm over $GF(q)$, for q a prime or prime power. The generalized algorithm, like its predecessor, is deterministic, given a primitive element $\omega $ for $GF(q)$. If $q - 1$ is b-smooth, where $b = (\log q)^{O(1)} $, then the algorithm runs in polynomial time. An analogue of this generalization which applies to extension fields $GF(q^m )$ is also considered. The analogue is a deterministic algorithm based on the recently introduced affine method for root finding in $GF(q^m )$, where $m > 1$; it is, however, less efficient that the affine method itself.
---
paper_title: Deterministic Analysis of Aleatoric Methods of Polynomial Factorization over Finite Fields

paper_content:

Abstract We analyze the problem of finding the roots of an arbitrary polynomial over a finite field (equivalent to factoring an arbitrary polynomial over the field) and propose a deterministic approach which leads to a combinatorial problem whose satisfactory solution would yield a factoring method which is polynomial in the logarithm of the size of the field and the degree of the input polynomial.
---
paper_title: On the Deterministic Complexity of Factoring Polynomials over Finite Fields

paper_content:

We present a new deterministic algorithm for factoring polynomials over Zp of degree n. We show that the worst-case running time of our algorithm is O(p12(log p)2n2+∈), which is faster than the running times of previous determi nistic algorithms with respect to both n and p. We also show that our algorithm runs in polynomial time for all but at most an exponentially small fraction of the polynomials of degree n over Zp. Specifically, we prove that the fraction of polynomials of degree n over Zp for which our algorithm fails to halt in time O((log p)2n2+∈) is ((n log p)2/p). Consequently, the average-case running time of our algorithm is polynomial in n and log p.
---
paper_title: On polynomial factorization over finite fields

paper_content:

Let f(x) be a polynomial over a finite field F. An algorithm for determining the degrees of the factors of f(x) is presented. As in the Berlekamp algorithm (1968) for determining the factors of f(x), the Frobenius endomorphism on F[x]/(f(x)) plays a central role. Little-known theorems of Schwarz (1956) and Cesaro (1888) provide the basis for the algorithm we present. New and stream-lined proofs of both theorems are provided.
---
paper_title: Counting irreducible factors of polynomials over a finite field

paper_content:

Abstract Let F q [X] denote a polynomial ring in an indeterminate X over a finite field F q . Exact formulae are derived for (i) the number of polynomials of degree n in F q [X] with a specified number of irreducible factors of a fixed degree r in F q [X] and (ii) the average number of such irreducible factors and corresponding variance for a polynomial of degree n in F q [X] . The main emphasis is on the case when multiplicity of factors is counted. These results are then applied to derive the mean and variance for the total number of irreducible factors of polynomials of degree n in F q [X] .
---
paper_title: Factorization of the General Polynomial by Means of Its Homomorphic Congruential Functions

paper_content:

The discovery of linear factors of polynomials is ordinarily accomplished by synthetic division, using factors of the constant term as trial divisors. When these factors are few the method is practical, even if not elegant. It is impractical in more general cases, however, when the coefficients are large or the factors are numerous or nonlinear. This implies the need for a general scheme which will discover factors of any degree more quickly and with less indirection. We advance here a theory and a method to determine the reducibility of the general polynomial P by a study of its reduced analog Pm. The scheme yields a procedure for determining the possible pattern of factors and also an exact determination of those factors, if any. We propose to set up the correspondence a--am which carries each integer a into its residue class modulo m, where m is a prime. This is a homomorphism of the ring of integers to the finite ring of integers Am. We then consider the general polynomial P with rational integral coefficients. The correspondence P--+Pm carries P into a finite ring of polynomials, with coefficients in Am. Use will be made here of the following theorems: I. If a polynomial P is reducible into rational integral factors, then Pm is similarly reducible in Am, where Am is the ring of integers modulo m, and Pm is the polynomial P with its coefficients reduced modulo m, (m a prime). II. The factors of Pm are congruent to the factors of P modulo m. III. If Pm is irreducible in Am, then P is irreducible over the rational integers (contrapositive of I). The following simplified proof of these principles uses linear factors but may easily be generalized: Let
---
paper_title: On a new factorization algorithm for polynomials over finite fields

paper_content:

A new deterministic factorization algorithm for polynomials over finite fields was recently developed by the first author. The bottleneck in this algorithm is the last stage in which the irreducible factors of the polynomial are derived from the solutions of a system of linear equations. An efficient approach to the last stage was designed by the second author for the case of finite fields of characteristic 2. In this paper, we describe a different approach to the last stage which works for arbitrary fields of positive characteristic. In particular, we obtain in this way an acceleration of the factorization algorithm of the first author which makes this algorithm polynomial time for fixed characteristic
---
paper_title: Distinct degree factorizations for polynomials over a finite field

paper_content:

Let Fq[X] denote the multiplicative semigroup of monic polynomials in one indeterminate X, over a finite field Fq . We determine for each fixed q and fixed n the probability that a polynomial of degree n in Fq[X] has irreducible factors of distinct degrees only. These results are of relevance to various polynomial factorization algorithms.
---
paper_title: Primer-Field Complete Functions and Factoring Polynomials over Finite Fields

paper_content:

We relate the arithmetic straight-line complexity over a field GF(p) (p is a prime) of the parity function l p to the Boolean complexity of the problem of factoring polynomials over finite fields of characteristic p. A procedure is described which -converts an arithmetic straight-line program for l p into a factoring algorithm. As a consequence, a short straight-line program for l p would imply the existence of an efficient factoring method.
---
paper_title: Factoring Polynomials over a Finite Field

paper_content:

The number of irreducible factors of a given monic polynomial $f( x )$ over $GF( q )$ is equal to the dimension of the space of characteristic sequences associated with $f( x )$. A basis for this space can be used to obtain the irreducible factors.
---
paper_title: FAST16 : A software program for factorising polynomials over large GF(p)

paper_content:

We propose experimental results, obtained from an algorithm for factorising polynomial over large prime fields GF (p).
---
paper_title: Deterministic Irreducibility Testing of Polynomials over Large Finite Fields

paper_content:

We present a sequential deterministic polynomial-time algorithm for testing dense multivariate polynomials over a large finite field for irreducibility. All previously known algorithms were of a probabilistic nature. Our deterministic solution is based on our algorithm for absolute irreducibility testing combined with Berlekamp's algorithm.
---
paper_title: Factorization of Polynomials over Finite Fields and Characteristic Sequences

paper_content:

Abstract A new factorization algorithm for polynomials over finite fields was recently developed by the first author. For finite fields of characteristic 2, it is known from previous work that this algorithm has several advantages over the classical Berlekamp algorithm. In this paper we show that the linearization step in the new algorithm is feasible—in the sense that it can be carried out in polynomial time—for arbitrary finite fields, by using an approach based on decimation operators and characteristic linear recurring sequences. We also introduce a general principle for the linearization of the factorization problem for polynomials over finite fields.
---
paper_title: Computing Zeta Functions Over Finite Fields

paper_content:

In this report, we discuss the problem of computing the zeta func- tion of an algebraic variety defined over a finite field, with an emphasis on computing the reduction modulo p m of the zeta function of a hypersurface, where p is the characteristic of the finite field.
---
paper_title: Parallel univariate polynomial factorization on shared-memory multiprocessors

paper_content:

Using parallelism afforded by shared-memory multiprocessors to speed up systems for polynomial factorization is discussed. The approach is to take the fastest known factoring algorithm for practical purposes and parallelize key parts of it. The univariate factoring algorithm consists of two major tasks (a) factoring modulo small integer primes and (b) EEZ lifting and recovery of true factors. A C coded system PFACTOR that implements (a) in parallel is described in detail. PFACTOR is a stand-alone parallel factorizer that can take input from a file, a pipe or a socket connection over a network. It can also be used interactively as a UNIX command. PFACTOR consists of parallel selection of primes, automatic balancing of work, parallel Berlekamp algorithm, and parallel reconciliation of degrees of factors modulo different primes. Actual timings on the Encore Multimax show the effectiveness of the approach. Work on part (b) is still on going.
---

Title: On Factoring Polynomials Over Finite Fields: A Survey
Section 1: Introduction
Description 1: This section will introduce the survey, define the problem of factoring polynomials over finite fields, discuss its importance, and give an overview of the paper's structure.

Section 2: A General Factoring Algorithm
Description 2: This section will describe the general framework of polynomial factorization algorithms, including the basic operations and stages required.

Section 3: Squarefree Factorization
Description 3: This section will discuss algorithms for obtaining the squarefree factorization of a polynomial, which is a crucial first step in the factorization process.

Section 4: Distinct-Degree Factorization
Description 4: This section will elaborate on methods for splitting a polynomial into factors that all have the same degree.

Section 5: Equal-Degree Factorization
Description 5: This section will present algorithms for further factoring polynomials when the irreducible factors have the same degree, with emphasis on probabilistic methods.

Section 6: Algorithms Based on Linear Algebra
Description 6: This section will cover advanced algorithms that utilize concepts from linear algebra, such as Berlekamp's algorithm and others, to factor polynomials.

Section 7: Polynomial Factorization Algorithms
Description 7: This section will provide a comprehensive list and brief descriptions of various polynomial factorization algorithms developed over the years.

Section 8: Probabilistic Algorithms
Description 8: This section will delve into the history and development of probabilistic algorithms for polynomial factorization, highlighting key contributions.

Section 9: Deterministic Algorithms
Description 9: This section will outline deterministic algorithms for polynomial factorization, including their theoretical foundations and performance.

Section 10: Average-Case Analysis
Description 10: This section will explore the average-case analysis of polynomial factorization algorithms, including studies on the distribution of irreducible factors.

Section 11: Further References
Description 11: This section will provide additional references and works not cited in the main text for readers interested in further exploring the topic.