key: cord-0047260-wtjz00bq
authors: Abbott, John
title: Certifying Irreducibility in [Formula: see text]
date: 2020-06-06
journal: Mathematical Software - ICMS 2020
DOI: 10.1007/978-3-030-52200-1_46
sha: c40b7d23a6c005ab11aa812d9d43567140feedeb
doc_id: 47260
cord_uid: wtjz00bq

We consider the question of certifying that a polynomial in [Formula: see text] or [Formula: see text] is irreducible. Knowing that a polynomial is irreducible lets us recognise that a quotient ring is actually a field extension (equiv. that a polynomial ideal is maximal). Checking that a polynomial is irreducible by factorizing it is unsatisfactory because it requires trusting a relatively large and complicated program (whose correctness cannot easily be verified). We present a practical method for generating certificates of irreducibility which can be verified by relatively simple computations; we assume that primes and irreducibles in [Formula: see text] are self-certifying.

A certificate that object X has property P is a "small" amount of extra information C such that some quick and simple computations with X and C suffice to confirm that X does have the property. We illustrate this vague definition with a well-known, concrete example. Example 1. We can certify that a positive integer n is prime using a Lucas-Pratt certificate [9] . The idea is to find a witness w such that w n−1 ≡ 1 mod n and w (n−1)/q ≡ 1 mod n for all prime factors q of n − 1.

These certificates have a recursive structure, since in general we must certify each prime factor q of n − 1. To avoid infinite recursion we say that all small primes up to some limit are "self-certifying" (i.e. they need no certificate).

Thus a Lucas-Pratt certificate comprises a witness w, and a list of prime factors q 1 , q 2 , . . . of n − 1 (and certificates for each q j ). Verification involves:

-verify that w n−1 ≡ 1 mod n; -verify that each w (n−1)/qj ≡ 1 mod n; -verify that n − 1 = j q ej j for positive exponents e j ; -recursively verify that each q j is prime.

The operations required to verify such a certificate are: iteration over a list, exponentiation modulo an integer, comparison with 1, division of integers, and divisibility testing of integers. These are all simple operations, and the entire function to verify a Lucas-Pratt certificate is small enough to be fully verifiable itself.

An important point in this example is that the certificate actually involves several cases: namely, if the prime is small enough, the certificate just says that it is a "small prime" (e.g. we can verify by table-lookup); otherwise the certificate contains a non-trivial body. In this instance there are just two possible cases.

We note that generating a Lucas-Pratt certificate could be costly because the prime factorization of n − 1 must be computed.

The total cost of a certificate comprises several components: -computational cost of generating the certificate; -size of the certificate (e.g. cost of storage or transmission); -computational cost of verification given the certificate; -size and code complexity of the verifier.

In the case of certifying the irreducibility of a polynomial in Z[x] we could issue trivial certificates for all polynomials, and say that the verifier simply has to be an implementation of a polynomial factorizer. We regard this as unsatisfactory because the size and code complexity of the verifier are too high.

We can immediately reduce from Q[x] to Z[x] thanks to Gauss's Lemma (for polynomials): let f ∈ Q[x] be non-constant then f is irreducible if and only if prim(f ) ∈ Z[x] is irreducible, where prim(f ) = αf and the uniquely defined, non-zero factor α ∈ Q is such that all coefficients of prim(f ) are integers with common factor 1, and the leading coefficient is positive,

The problem of certifying irreducibility in Z[x] has a long history, and has already been considered by several people. Here is a list of some approaches: -give a "large" evaluation point n such that f (n) has a large prime factor; -degree analysis (from factorizations over one or more finite fields) 1 ; -a linear polynomial is obviously irreducible; -Newton polygon methods (e.g. Schönemann, Eisenstein, and Dumas [4] ); -Vahlen-Capelli lemma [10] for binomials -Perron's Criterion [8] ; -the coefficients are (non-negative) digits of a prime to some base b (e.g. [8] ).

The first technique in the list was inspired by ideas from [3] ; it seems to be new.

In this presentation, we shall assume that the degree is at least 2, and shall concentrate on the first two methods as they are far more widely applicable than others listed.

Factor degree analysis is a well-known, behind-the-scenes technique in polynomial factorization. It involves using degrees of modular factors to obtain a list of excluded degrees for factors in Z[x].

We define a factor degree lower bound for f ∈ Z[x] to be Δ ∈ N such that we have excluded all degrees less than Δ, e.g. through factor degree analysis. We can certify this lower bound by accompanying it with the modular factorizations used. Clearly, if degree analysis excludes all degrees up to 1 2 deg f then we have proved that f is irreducible. Finally, we may always take Δ = 1 without any degree analysis.

In many cases we can indeed prove/certify irreducibility via degree analysis. However, there are some (infinite) families of polynomials where one must use "larger" primes, and there are also (infinite) families where irreducibility cannot be proved via factor degree analysis (e.g. resultants, in particular Swinnerton-Dyer polynomials, see also [6] ).

Example 2. The well-known, classical example of a polynomial which cannot be proved irreducible by degree analysis is x 4 + 1: every modular factorization is into either 4 linears or 2 quadratics, so this does not let us exclude the possible existence of a degree 2 factor.

There are also many polynomials which can be proved irreducible by degree analysis, but are not irreducible modulo any prime; this property depends on the Galois group of the polynomial. For instance, f = x 4 + x 3 + 3x + 4 is one such polynomial: modulo 2 the irreducible factors have degrees 1 and 3, and modulo 5 both factors have degree 2; but it is never irreducible modulo p.

Degree Analysis Certificate. A degree analysis certificate comprises -a subset D ⊆ {1, 2, . . . , 1 2 deg f } of "not excluded" factor degrees -a list, L, of pairs: a prime p, and the irreducible factors of f modulo p If D = ∅, we have a certificate of ireducibility; otherwise the smallest element of the set is a factor degree lower bound.

Verification of the certificate involves the following steps:

-for each entry in L, check that the product of the modular factors is f ; -for each entry in L, compute the set of degrees of all possible products of the modular factors; verify that their intersection is D; -check that each modular factor is irreducible (e.g. use gaussian reduction to compute the rank of B − I where B is the Berlekamp matrix).

The main cost of the verification is the computation of B and the rank of B − I; the cost of computing B is greater for larger primes, so we prefer to generate certificates which use smaller primes if possible.

We would like to know, in practice, how costly it is to produce a useful degree analysis certificate, and how large the resulting certificate could be. More specifically:

-How many different primes should we consider? And how large? -How to find a minimal set of primes yielding the factor degree subset? -How many primes are typically in the minimal set?

In our experience, a minimal length list very rarely contains more than 3 entries, but we should expect to consider many more primes during generation of the certificate. We can construct irreducible polynomials which require considering "large" primes to obtain useful degree information (e.g. x 2 + Nx + N where N = 1000000!) but in many cases "small" primes up to around deg f suffice.

Bunyakowski's conjecture (e.g. see page 323 of [7] ) states that if f ∈ Z[x] is irreducible (and has trivial fixed divisor) then |f (n)| is prime for infinitely many n ∈ Z. Assuming the conjecture is true, we can get a certificate of irreducibility by finding a suitable evaluation point n (and perhaps including a certificate that |f (n)| is prime). Applying Bunyakowski's conjecture directly is inconvenient for two reasons:

-we want to handle polynomials with non-trivial fixed divisor; -finding a suitable n may be costly, and the resulting |f (n)| may be large.

The first point is solved by an easy generalization of the conjecture: let f ∈ Z[x] be irreducible and δ be its fixed divisor, then there are infinitely many n ∈ Z such that |f (n)|/δ is prime. The second point is a genuine inconvenience: for some polynomials, it can be costly to find a "Bunyakowski prime," and the prime itself will be large (and thus costly to verify). For example, let f = x 16 +4x 14 +6x 2 +4 then the smallest good evaluation point is n = 6615, and |f (n)| ≈ 1.3 × 10 61 .

Here we present a much more practical way of certifying irreducibility by evaluation: we require just a sufficiently large prime factor. Let f ∈ Z[x] be non-constant, and let ρ ∈ Q be a root bound for f : that is, for every α ∈ C such that f (α) = 0 we have |α| ≤ ρ. We note that it is relatively easy to compute root bounds (e.g. see [2] ). The following proposition was partly inspired by Theorem 2 in [3] , but appears to be new.

Proof. For a contradiction, suppose that f = gh ∈ Z[x] is a non-trivial factorization. We may assume that

where d = deg f , C f ∈ Z is the leading coefficient, and the α j are the roots of f in C. We may assume that the α j are indexed so that the roots of g are α 1 , . . . , α dg where d g = deg g.

By evaluation we have f (n) = g(n) h(n) with all values in Z. Also f (n) = 0 since |n| > ρ. We now estimate |g(n)|:

where C g ∈ Z is the leading coefficient. Each factor in the product has magnitude greater than 1, so |g(n)| ≥ (|n|−ρ) Δ > s. Similarly, |h(n)| > s. This contradicts the given factorization f (n) = sp.

When we have an evaluation point to which Proposition 1 applies we call it a large prime factor witness (abbr. LPFW) for f, ρ and Δ. We conjecture that every irreducible polynomial has infinitely many LPFWs; note that Bunyakowski's conjecture implies this.

Example 3. This example shows that it can be beneficial to look for large prime factor witnesses rather than Bunyakowski prime witnesses.

Let f = x 12 + 12x 4 + 92 and take Δ = 1. We compute ρ = 7 4 as root bound, and then we obtain a LPFW at n = 5 with prime factor p = 81382739. In contrast, the smallest Bunyakowski prime is ≈ 3.06 × 10 41 at n = 2865.

In the light of this example we exclude consideration of a certificate based on Bunyakowski's conjecture, and consider only LPFWs.

We prefer to issue an LPFW certificate where the prime p is as small as "reasonably possible". Our implementation searches for suitable n in an incremental way, since smaller values of |n| produce smaller values of |f (n)|, and we expect smaller values of |f (n)| to be more likely to lead to an "sp" factorization with small prime factor p-this is only a heuristic, and does not guarantee to find the smallest such p. We look for the factorization |f (n)| = sp by trial division by the first few small primes (and GMP's probabilistic prime test for p).

LPFW Certificate. An LPFW certificate comprises the following information:

-a root bound ρ, -a factor degree lower bound Δ ←− with degree analysis certificate, -the evaluation point n > 1 + ρ, -the large prime factor p of |f (n)| ← − (opt.) with certificate of primality.

Verification of an LPFW certificate entails:

-evaluating f (n) and verifying that p is a factor; -verifying that the discarded factor s = |f (n)|/p satisfies s < (|n| − ρ) Δ ; -verifying that ρ is a root bound for f ←− see comment below; -(if Δ > 1) verifying that Δ is a factor degree lower bound; -verifying that p is (probably) prime.

In many cases the root bound can be verified simply by evaluation of a modified polynomial: let f (x) = d j=0 a j x j and set f * (x) = |a d |x d − d−1 j=0 |a j |x j , then if f * (ρ) > 0 then ρ is a root bound for f . Some tighter root bounds may require applying an (iterated) Gräffe transform to f first (e.g. see [2] ).

Example 4. This example shows how degree information can be useful in finding a small LPFW. Let f = x 4 − 1036x 2 + 7744. We find that ρ = 33 is a root bound. Without degree information (i.e. taking Δ = 1) we obtain the first LPFW at n = 65 with corresponding prime p = 13481269. In contrast, from the factorization of f modulo 3 we can certify that Δ = 2 is a factor degree lower bound for f . This information lets us obtain an LPFW at n = 47 with far smaller corresponding prime p = 14519.

We define a (minor generalization of) a Möbius transformation for Z[x]. The crucial property for us is that these transformations preserve irreducibility (except for some polynomials of degree 1).

In our applications the matrix entries will be integers, and we shall suppose that at least one of a and c is non-zero.

μ M is degenerate if det M = 0.

Here is a summary of useful properties of a Möbius transformation μ M . For part (f), suppose we have a counter-example f ∈ Z[x], then we have a non-trivial factorization μ M (f ) = gh, but by (b) and (d) we deduce that

which is a non-trivial factorization, contradicting the assumption that f was irreducible.

Our interest in Möbius transformations is that they offer the possibility of finding a better LPFW certificate. Unfortunately we do not yet have a good way of determining which Möbius transformations are helpful.

Example 5. Let f = 97x 4 + 76x 3 + 78x 2 + 4x + 2. We obtain a LPFW certificate with ρ = 7/5, Δ = 1, n = −4 with corresponding prime factor p = 10601.

Let M = 1 1 −3 2 . Let g = prim(μ M (f )) = (x 4 + 1); by Proposition 2.(f) since deg g = deg f a LPFW certificate for g also certifies that f is irreducible. For g we obtain a certificate with ρ = 1, Δ = 1, n = 2 with much smaller corresponding prime factor p = 17.

Unsolved Problem: How to find a good Möbius matrix M given just f ?

Naturally, if we generate a LPFW certificate for a transformed polynomial μ M (f ) then we must indicate which Möbius transformation was used. Given two polynomials f, g ∈ Z[x] of the same degree d, and M ∈ Mat 2×2 (Z), one can easily verify that g = prim(μ M (f )) by evaluating f at deg(f ) distinct rational points, and g at the (rational) transforms of these points, and then checking that the ratios of the values are all equal. So the extra information needed is M and μ M (f ).

Some content-free polynomials have non-trivial fixed divisors: an example is f = x 2 + x + 2 which is content-free but has fixed divisor 2.

Proof. The standard proof follows easily from representating of f with respect to the "binomial basis" for Z[x], namely { x k | k ∈ N}.

Polynomials having large fixed divisor δ cannot have small LPFW certificates because we are forced to choose large evaluation points since we must have (|n| − ρ) Δ > δ. This problem becomes more severe for higher degree polynomials since the fixed divisor can be as large as d! where d is the degree.

We can reduce the size of the fixed divisor by scaling the indeterminate (i.e. a Möbius transformation for a diagonal matrix), or perhaps reversing the polynomial and scaling the indeterminate (i.e. a Möbius transformation for an anti-diagonal matrix). We have not yet investigated the use of more general Möbius transformations.

Let f ∈ Z[x] be content-free, irreducible with fixed divisor δ. Let q be a prime factor of δ, and let k be the multiplicity of q in |f (0)|. Then

has fixed divisor δ/q k . In practice, we consider several polynomials obtained by scaling x by q 1 , q 2 , . . . , q k ; in fact scaling by q −1 , q −2 , . . . can also be beneficial.

Our prototype implementation runs degree analysis and LPFW search "in parallel": i.e. it repeatedly alternates a few iterations of degree analysis with a few iterations of LPFW search. If degree analysis finds a new factor degree lower bound, Δ, this information is passed to the LPFW search.

We adopted the following strategy for choosing primes during degree analysis: initially we create a list of "preferential primes" (e.g. including the first few primes greater than the degree), then we pick primes alternately from this list or from a random generator. The range for randomly generated primes is gradually increased to favour finding quickly a certificate involving smaller primes (since these are computationally cheaper to verify). This strategy was inspired by some experimentation. There exist polynomials whose degree analysis certificates must involve "large" primes: e.g. a good set of primes for x 4 + 16x 3 + 5x 2 − 14x − 18 must contain at least one prime greater than 101. Also, empirically we find that a degree analysis certificate for an (even) Hermite polynomial must use primes greater than the degree.

To issue a certificate, we look for a minimal cardinality subset of the primes used which suffices. This subset search is potentially exponential, but in our experiments it is very rare for a minimal subset to need more than 3 primes.

As already mentioned, not all polynomials can be certified irreducible by degree analysis. A well-known class of polynomials for which irreducibility cannot be shown by degree analysis are the Swinnerton-Dyer polynomials: they are the minimal polynomials for sums of square-roots of "independent" integers. A more general class of such polynomials was presented in [6] .

We saw in Example 5, it can be better to issue a LPFW certificate for a transformed polynomial, but we do not yet have a good way of finding a good Möbius transformation. Our current prototype implementation considers only indeterminate scaling and possibly reversal: i.e. the Möbius matrix must be diagonal or anti-diagonal. A list of all scaling and reverse-scaling transforms by "simple" rationals is maintained, and the resulting polynomials are considered "in parallel". For each transformed polynomial we keep track of two evaluation points (one positive, one negative) and the corresponding evaluations. The evaluations are then considered in order of increasing absolute value; once an evaluation has been processed the corresponding evaluation point is incremented (or decremented, if it is negative).

The LPFW search depends on a factor degree lower bound, Δ, which is initially 1. The degree analysis "thread" may at any time furnish a better value for Δ. So that this asynchrony can work well the LPFW search records, for each possible factor degree lower bound, any certificates it finds. When a higher Δ is received, the search first checks whether a corresponding LPFW certificate has already been recorded; if so, that certificate is produced as output. Otherwise searching proceeds using the new Δ.

Here are a few examples as computed by the current prototype, since degree analysis picks primes in a pseudo-random order different certificates may be issued for the same polynomial. A quick comment about run-times: our interpreted prototype favours producing certificates which are cheap to verify (rather than cheap to generate); the degree analysis certificates took ∼ 0.25 s each to generate, the others ∼ 0.5 s each. We did not measure verification run-time, but fully expect it to be less than 0.01 s in each case. In comparison, the polynomial factorizer in CoCoA took less than 0.01 s for all of these polynomials.

As a larger example: the prototype took ∼ 20 s (we expect the final implementation to be significantly faster) to produce a certificate for the degree 64 (Swinnerton-Dyer) minimal polynomial of √ 61 + √ 79 + √ 139 + √ 181 + √ 199 + √ 211

This polynomial has fixed divisor δ = 2 29 5 14 13 4 ≈ 1.2 × 10 28 . Our prototype found and applied the transformation x → 52 15 x, then produced an LPFW certificate for the transformed polynomial: ρ = 451/16, Δ = 2 (with L = [19]), n = 46 and p ≈ 7.5 × 10 180 which was confirmed to be "probably prime" (according to GMP [5] ). The classical Berlekamp-Zassenhaus factorizer in CoCoA [1] took about 300 s to recognize irreducibility.

An anonymous referee reasonably asked about expected run-time or a (possibly heuristic) complexity analysis. The answer is "It depends . . . ". For "almost all" polynomials, degree analysis suffices and is quick. In our setting, the LPFW search effectively happens only if a degree analysis certificate cannot be quickly found. In our experiments, the number of iterations in LPFW search before producing a certificate was quite irregular.

As mentioned in the introduction there are many different criterions for certifying the irreducibility of a polynomial in Z[x]. Here we have concentrated on just two of them, and have pointed out how they can "collaborate".

We have built a prototype implementation in CoCoA [1] , and plan to integrate it into CoCoALib, the underlying C++ library (where we expect significant performance gains).

An interesting future possibility is for the requester of the certificate to state which criterions may be used (dictated by the implemented verifiers that the requester has available). But, a too restrictive choice of criterions may make it impossible to generate a certificate: e.g. there is no "Eisenstein" certificate for most polynomials.

CoCoA: a system for doing Computations in Commutative Algebra

Bounds on factors in Z

Heugcd: how elementary upperbounds generate cheaper data

Sur quelques cas d'irréductibilité des polynomesà coefficients rationnels

GNU multiprecision library

A generalized class of polynomials that are hard to factor

Algebra, 3rd edn

Neue Kriterien für die Irreduzibilität algebraischer Gleichungen

Every prime has a succinct certificate

New proofs for two theorems of Capelli