Refereed. Pages 27–34 in Algorithmic number theory: ANTS-II, edited by Henri Cohen, Lecture Notes in Computer Science 1122, Springer, 1996. Fast ideal arithmetic via lazy localization

Daniel J. Bernstein

Department of Mathematics, Statistics, and Computer Science, The University of Illinois at Chicago, Chicago, IL 60607–7045

                             djb@math.uic.edu

Abstract. This paper proposes a new representation for ideals of any order in an algebraic number field. This representation is compact and highly readable; for example, (95, x+65)(221^{6}) and (7, x^{2} +4)(95, x+46) are two ideals of Z[x]/(x^{4} − x^{3} + 7x^{2} − 11x + 5), with sum (19, x + 8). Arithmetic on ideals in this form is generally much faster than arithmetic in the Z-basis or two-element representations.

1 Introduction

I propose a new, highly readable representation for ideals of any order in a number field. Arithmetic in this representation is generally much faster than arithmetic in the Z-basis or two-element representations.

The idea is as follows. Any nonzero ideal contains some positive integer N. Represent the ideal locally at all the primes of Z dividing N. This representation is compatible with arithmetic: all the usual ideal operations are local.

It is not possible in practice to find the set of primes dividing N. So, following a philosophy of Hendrik W. Lenstra, Jr., I work instead with a coprime base P for N: a pairwise coprime set of positive integers generating a semigroup that contains N. (Initially P may be taken as {N}.) A typical p ∈ P might not be prime, but I nevertheless think of p as prime—until encountering a nonzero nonunit modulo p, at which point I factor p and continue the computation.

To add or multiply or intersect two ideals one must first find a common coprime base for them. This can be done in essentially linear time; see [1]. Once the ideals are represented on a common coprime base, all operations are “local”; see section 4.

Throughout this paper φ ∈ Z[x] is an irreducible monic integer polynomial. The ring Z[x]/φ is an order inside the number field Q[x]/φ. Most of this paper focuses on the representation of ideals of Z[x]/φ. For fractional ideals see section 8. For orders bigger than Z[x]/φ see section 9.

In this paper, all rings are commutative.

Thanks to Hendrik W. Lenstra, Jr., for his helpful comments.

2 Flat modules

The reader willing to accept Lemma 3.1 and Lemma 3.3 without proof may skip this section.

Let R be a ring, M an R-module. For any subgroup G of R^{n}, write MG for the subgroup of M^{n} generated by {mg : m ∈ M, g ∈ G}.

Definition: M is flat over R if the M-kernel of any R-matrix is M-generated by the R-kernel. In other words, if M is flat over R, and A is an n-column matrix with coefficients in R, and z ∈ M^{n} satisfies Az = 0, then z is in M {x ∈ R^{n} : Ax = 0}. See [3, Theorem 7.6].

Lemma 2.1. Let R be a ring, M a flat R-module. Let I and J be R-submodules of R^{n}. Then MI ∩ MJ = M(I ∩ J).

Proof. It suffices to show that MI ∩ MJ ⊆ M(I ∩ J). Take t ∈ MI ∩ MJ. By definition of MI, there are elements b_{1}, b_{2}, …, b_{r} ∈ M and g_{1}, g_{2}, …, g_{r} ∈ I with t = b_{1}g_{1} + b_{2}g_{2} + ⋯ + b_{r}g_{r}. Similarly there are elements c_{1}, c_{2}, …, c_{s} ∈ M and h_{1}, h_{2}, …, h_{s} ∈ J with t = c_{1}h_{1} + c_{2}h_{2} + ⋯ + c_{s}h_{s}.

Let A be the matrix for the map R^{n} ×R^{r} ×R^{s} → R^{n} ×R^{n} that takes (y, d, e) to (y − d_{1}g_{1} − ⋯ − d_{r}g_{r}, y − e_{1}h_{1} − ⋯ − e_{s}h_{s}). Note that if A(y, d, e) = 0 then y ∈ I ∩ J.

Now the vector z = (t, b_{1}, b_{2}, …, b_{r}, c_{1}, c_{2}, …, c_{s}) satisfies Az = 0. By flatness, z is a combination with coefficients in M of vectors x ∈ R^{n} × R^{r} × R^{s} satisfying Ax = 0. Hence t is the same combination of vectors y ∈ I ∩ J. ⊓ ⊔

Lemma 2.2. Let R be a ring, B a flat extension of R. Let I be an R-submodule of R^{n}. If x ∈ BI ∩R^{n} then 1 = b_{1}m_{1} +b_{2}m_{2} +⋯+b_{s}m_{s} for some b_{1}, b_{2}, …, b_{s} ∈ B and m_{1}, m_{2}, …, m_{s} ∈ R with m_{1}x, m_{2}x, …, m_{s}x ∈ I.

Proof. By definition of BI, there are coefficients c_{1}, c_{2}, …, c_{r} ∈ B and elements g_{1}, g_{2}, …, g_{r} ∈ I with x = c_{1}g_{1} + ⋯ + c_{r}g_{r}. Let A be the matrix for the map R×R^{r} → R^{n} that takes (m, d) to mx−d_{1}g_{1}−⋯−d_{r}g_{r}. Note that if A(m, d) = 0 then mx ∈ I.

Now the vector z = (1, c_{1}, …, c_{r}) satisfies Az = 0. By flatness, there are coefficients b_{1}, …, b_{s} ∈ B and vectors (m_{1}, d_{1}), …, (m_{s}, d_{s}) ∈ R × R^{r} satisfying A(m_{i}, d_{i}) = 0 and z = b_{1}(m_{1}, d_{1}) + ⋯ + b_{s}(m_{s}, d_{s}). In particular m_{i}x ∈ I and 1 = b_{1}m_{1} + ⋯ + b_{s}m_{s}. ⊓ ⊔

3 The ring Z_{p}

Let p be an integer. The completion of Z at p, written Z_{p}, is the projective limit of Z/p^{n}. An element of Z_{p} is a sequence (x_{1}, x_{2}, …), with x_{n} ∈ Z/p^{n}, such that x_{n+1} mod p^{n} = x_{n}. For p > 1, Z_{p} is an extension of Z.

Z_{p} is flat over Z. This follows from the fact that Z_{p} is torsion-free. Indeed, Z is a Prüfer domain—any torsion-free Z-module is flat. (Any Dedekind domain is a Prüfer domain; see [3, Exercise 11.8].)

More generally, any completion of a Noetherian ring is flat. See [3, Theorem 8.8].

Lemma 3.1. Let p be an integer. Let I and J be subgroups of Z^{n}. Then Z_{p}I ∩ Z_{p}J = Z_{p}(I ∩ J).

Proof. Lemma 2.1. ⊓ ⊔

Lemma 3.2. Let p > 1 be an integer. If Q ∈ Z_{p} and p^{e}Q ∈ Z then Q ∈ Z.

Proof. The image of p^{e}Q in Z/p^{e} is 0, so p^{e}Q is divisible by p^{e} in Z; let q ∈ Z be the quotient. Now p^{e}(q − Q) = 0, but Z_{p} is torsion-free, so q = Q. ⊓ ⊔

Lemma 3.3. Let p and u be integers with p > 1. Let I be a subgroup of Z^{n} containing p^{e}uZ^{n}. Then u(Z_{p}I ∩ Z^{n}) ⊆ I.

Proof. Pick x ∈ Z_{p}I ∩ Z^{n}. By Lemma 2.2 there are b_{1}, b_{2}, …, b_{s} ∈ Z_{p} and m_{1}, m_{2}, …, m_{s} ∈ Z such that m_{i}x ∈ I and 1 = b_{1}m_{1} + b_{2}m_{2} + ⋯ + b_{s}m_{s}. Write b_{i} = p^{e}q_{i} + r_{i} with q_{i} ∈ Z_{p} and r_{i} ∈ Z, and define Q = q_{1}m_{1} + ⋯ + q_{s}m_{s}; then 1 = p^{e}Q + r_{1}m_{1} + ⋯ + r_{s}m_{s}, so Q is an integer by Lemma 3.2. Finally ux = p^{e}uQx + ur_{1}m_{1}x + ⋯ + ur_{s}m_{s}x ∈ I. ⊓ ⊔

4 Ideals of Z[x]/φ versus ideals of Z_{p}[x]/φ

For any ideal I of Z[x]/φ consider Z_{p}I, the smallest subgroup of Z_{p}[x]/φ containing {ci : c ∈ Z_{p}, i ∈ I}. Z_{p}I is an ideal of Z_{p}[x]/φ.

If I is generated by β then Z_{p}I is generated by the image of β in Z_{p}[x]/φ. If J is another ideal of Z[x]/φ then Z_{p}(I + J) = Z_{p}I + Z_{p}J; Z_{p}(IJ) =

(Z_{p}I)(Z_{p}J); and, by Lemma 3.1, Z_{p}(I ∩ J) = Z_{p}I ∩ Z_{p}J.

Lemma 4.1. Let p > 1 be an integer. Let I be a nonzero ideal of R = Z[x]/φ. Then the natural map R → Z_{p}[x]/φ induces an isomorphism R/(Z_{p}I ∩ R) → (Z_{p}[x]/φ)/Z_{p}I.

Proof. Let f be the natural map from R to (Z_{p}[x]/φ)/Z_{p}I. It is enough to show that f is surjective.

Since I is nonzero it contains some positive integer N. Given any g ∈ Z_{p}[x]/φ, write g = qN + r with q ∈ Z_{p}[x]/φ and r ∈ R. Then qN ∈ Z_{p}I so g mod Z_{p}I = f(r). ⊓ ⊔

Lemma 4.2. Let I be an ideal of R = Z[x]/φ containing a positive integer N. Let P be a coprime base for N. Then R/I is isomorphic to ∏_{p∈P −{1}}(R/(Z_{p}I ∩R)).

Proof. Z_{p}I ∩ R contains the maximum power of p dividing N, for p ∈ P. Hence Z_{p}I ∩ R and Z_{q}I ∩ R are coprime whenever p and q are coprime.

It thus suffices to show that I = ⋂_{p}(Z_{p}I ∩R). Certainly I ⊆ Z_{p}I ∩R. For the converse it is convenient to write u_{p} for the non-p-part of N; i.e., N is u_{p} times a power of p, and u_{p} is coprime to p. Now say β ∈ R is in Z_{p}I. By Lemma 3.3, u_{p}β ∈ I. If this is true for all p then β ∈ I since gcd {u_{p} : p ∈ P, p ≠ 1} = 1. ⊓ ⊔

5 A standard representation for ideals of Z_{p}[x]/φ

Let p > 1 be an integer. In this section I describe a standard representation for finite-norm ideals of Z_{p}[x]/φ. Not every ideal can be written in this representation, unless p is prime; however, there is an algorithm that, given generators for an ideal, either (1) finds a standard representation for the ideal or (2) finds a nontrivial factor of p. The algorithm appears in section 6.

I begin with the representation in [2, Theorem 4.7.5], which is an improvement (specific to ideals) of the Hermite normal form ([2, section 2.4.2]). Recall that a representation for I is a Z_{p}-basis for I of the form {c_{n}f_{n} : 0 ≤ n < deg φ}. Here f_{n} ∈ Z_{p}[x] is a monic polynomial of degree n, and c_{n} ∈ Z_{p} is some nonzero coefficient. (One can take c_{n} ∈ Z and f_{n} ∈ Z[x].)

I improve this representation in two ways. First, if several polynomials f_{n} have the same leading coefficient c_{n}, I record only the polynomial of lowest degree. The ideals of Z_{p}[x] that show up in practice seem to contain few distinct coefficients. This makes arithmetic much faster, at the expense of a more complicated implementation, for the simple reason that there are fewer numbers to manipulate. It also makes the output more readable, for the same reason.

Second, I insist that each leading coefficient be a power of p. This again improves speed and readability: I can store, manipulate, and print the exponent rather than the power. If p is not prime, there is no guarantee that one can successfully write an ideal this way, but failure reveals a nontrivial factor of p.

My representation is thus a sequence (d_{0}, e_{0}, f_{0}), (d_{1}, e_{1}, f_{1}), …, with 0 = d_{0} < d_{1} < ⋯ < deg φ, e_{0} > e_{1} > ⋯ ≥ 0, and f_{i} a monic integer polynomial of degree d_{i}, such that

I = p^{e_{0}}f_{0}Z_{p} + p^{e_{0}}f_{0}xZ_{p} + p^{e_{0}}f_{0}x^{2}Z_{p} + ⋯ + p^{e_{0}}f_{0}x^{d_{1}−1}Z_{p}
+ p^{e_{1}}f_{1}Z_{p} + p^{e_{1}}f_{1}xZ_{p} + p^{e_{1}}f_{1}x^{2}Z_{p} + ⋯ + p^{e_{1}}f_{1}x^{d_{2}−d_{1}−1}Z_{p}
+ p^{e_{2}}f_{2}Z_{p} + p^{e_{2}}f_{2}xZ_{p} + p^{e_{2}}f_{2}x^{2}Z_{p} + ⋯ + p^{e_{2}}f_{2}x^{d_{3}−d_{2}−1}Z_{p}
+ · · · .

I is generated as an ideal by p^{e_{0}}f_{0}, p^{e_{1}}f_{1}, . . .. The norm of I is #((Z_{p}[x]/φ)/I) = p^{e_{0}d_{1}+e_{1}(d_{2}−d_{1})+e_{2}(d_{3}−d_{2})+···}. One can impose bounds upon the coefficients of each f_{i} to make this representation unique; see [2, section 2.4.2].

In practice I display (p^{e_{0}}f_{0}, p^{e_{1}}f_{1}, …). Five examples of ideals, with φ = x^{4} − x − 3: (11, x + 5); (11, x^{2} + 3x + 1); (11^{2}, 11(x + 5), x^{2} + 91x + 12); (10^{25}); (65, x^{3} + 58x^{2} + 49x + 46).

6 Computing a representation for an ideal of Z_{p}[x]/φ

Let p > 1 be an integer. Let I be the ideal of Z_{p}[x]/φ generated by a finite set B. Assume that I contains a positive integer N. Given p, N, B, Algorithm 6.1 attempts to compute a standard representation for I. It may instead take a “side exit,” producing a nontrivial factor of p.

Algorithm 6.1 works with a set C of nonnegative integer polynomials contained in I. At the beginning of steps 3, 4, and 5, C has exactly one polynomial of each degree from 0 through deg φ − 1. The leading coefficient of each polynomial is a power of p.

Write M for the Z_{p}-module generated by C. Algorithm 6.1 uses a subroutine, Algorithm 6.2, which expands M to contain any given polynomial h, printing 1 if C was changed or 0 if h was already in M. Algorithm 6.1 repeatedly invokes Algorithm 6.2 to ensure that B ⊆ M and that M is closed under multiplication by x. Algorithm 6.1 and Algorithm 6.2 terminate because the norm of M, #((Z_{p}[x]/φ)/M), decreases whenever Algorithm 6.2 prints 1.

Algorithm 6.1.

1. Compute the maximum n such that p^{n} divides N. If N/p^{n} is not coprime to p, side exit: gcd {N/p^{n}, p} is a nontrivial factor of p.

2. (Now p^{n} ∈ I.) Set N ← p^{n}. Set C ← {N, Nx, Nx^{2}, …, Nx^{deg φ−1}}.

3. (Now C ∪ B generates I as an ideal.) For each β ∈ B: Apply Algorithm 6.2 to β.

4. (Now C generates I as an ideal.) For each g ∈ C: Apply Algorithm 6.2 to gx; if Algorithm 6.2 prints 1, go back to the beginning of step 4.

5. (Now C generates I as an ideal; and gx ∈ M for each g ∈ C. Thus M = I. Each polynomial in C is divisible by its leading coefficient, and by the leading coefficients of all higher-degree polynomials in C; see the proof of [2, Theorem 4.7.5].) Remove from C any polynomial whose leading coefficient appears on a polynomial of smaller degree. Now the set of (deg f, e, f), where e is an integer and f is a monic integer polynomial with p^{e}f ∈ C, is a standard representation for I.

Algorithm 6.2.

1. Set h ← (h mod φ) mod N.

2. (Now deg h < deg φ.) If h = 0: Print 0 and stop.

3. (Now 0 ≤ deg h < deg φ.) Let g be the polynomial in C with deg g = deg h. Set L to the leading coefficient of h. If the leading coefficient of g divides L, set h ← (h mod g) mod N and go back to step 2.

4. (Now 0 ≤ deg g = deg h < deg φ; g ∈ C; and the leading coefficient of g does not divide L, the leading coefficient of h. Thus h ∉ M.) Compute the maximum n such that p^{n} divides L. If L/p^{n} is not coprime to p, side exit: gcd {L/p^{n}, p} is a nontrivial factor of p.

5. Find integers u and v so that uh − vg has leading coefficient p^{n}. Set h ← (uh − vg) mod N. (Note that u is coprime to p; thus this does not change the Z_{p}-module generated by C ∪ {h}.)

6. Set C ← (C − {g}) ∪ {h}. (This decreases the norm of M.)

7. Apply Algorithm 6.2, recursively, to g.

8. Print 1.

In practice, step 4 of Algorithm 6.1 should tag each element g ∈ C for which gx is already known to be in M; then it can avoid feeding gx to Algorithm 6.2 more than once.

7 A representation for nonzero ideals of Z[x]/φ

Let I be a nonzero ideal of the ring R = Z[x]/φ. I propose to represent I by {(p, Z_{p}I) : p ∈ P }, where P is a coprime base (not containing 1) for some positive integer in I. This representation is compatible with computing principal ideals, ideal sums, and ideal norms; a fortiori it determines I.

In practice I display the concatenation of {Z_{p}I : p ∈ P }. For example, the ideal generated by 27075 and 3(x^{2} + 36x + 2010) modulo x^{4} − x^{3} + 7x^{2} − 11x + 5 is (3)(5^{2}, 5(x + 1), x^{2} + x)(19^{2}, 19(x + 9), x^{2} + 17x + 34).

Basic operations. To find the ideal generated by β ≠ 0: Let N be the absolute value of the norm of β. Set P = {N}. Then find a standard representation for the ideal generated by β in Z_{N}[x]/φ. (Exception: If N = 1, set P = {}.)

To find the norm #(R/I) of an ideal I: Multiply the local norms. By Lemma 4.1 and Lemma 4.2, #(R/I) = ∏_{p} #((Z_{p}[x]/φ)/Z_{p}I).

To add or multiply or intersect two ideals: Say they have coprime bases Q and Q′. Find a coprime base P for Q ∪ Q′, as discussed in [1], and split each ideal into P -pieces. Then find a standard representation for the sum or product or intersection of local pieces. For more details on intersection see [2, Exercise 4.18]; an alternate method appears in section 8.

As noted in section 5, some ideals of Z_{p}[x]/φ do not have a standard representation. Whenever Algorithm 6.1 or Algorithm 6.2 discovers a nontrivial factor q of p ∈ P, I replace p by a coprime base for {p, q}. Then I restart the computation.

Here is a numerical example. Fix φ = x^{4} − x^{3} + 7x^{2} − 11x + 5. Consider the ideals I = (95, x+65)(221^{6}) and J = (7, x^{2} +4)(95, x+46); what is I +J? I start with P = {7, 95, 221} and add the 7-pieces, 95-pieces, and 221-pieces separately. Focus on 95: the 95-piece of the sum is generated by 95, x + 65, 95, x + 46. I feed these generators to Algorithm 6.1, which discovers the factor 19 of 95, so I replace 95 with 5, 19 and restart. To split (95, x + 65) into a 5-piece and a 19-piece, I feed the generators 95, x+65 to Algorithm 6.1, first with p = 5, producing (5, x), and then with p = 19, producing (19, x + 8). Similarly, I split (95, x + 46) into (5, x + 1)(19, x + 8). Then I add the 5-pieces and 19-pieces separately. The final result is I + J = (19, x + 8).

Other operations. The above operations suffice to construct many further operations. For example, J ⊆ I if and only if #(R/(I + J)) = #(R/I); β ∈ I if and only if βR ⊆ I; J = I if and only if #(R/I) = #(R/J) = #(R/(I + J)). In practice it is better to implement these other operations separately.

8 Fractional ideals

I represent a fractional ideal as a nonzero ideal divided by an integer. It is convenient to break the integer into local pieces.

Fractional ideals admit several new operations. All of them are special cases of ratio: if I and J are subgroups of K = Q[x]/φ then the ratio J ÷ I = {x ∈ K : xI ⊆ J} is also a subgroup of K.

Define T = {x ∈ K : trace_{K:Q} x ∈ Z}. For any fractional ideal I, the ratio T ÷ I is also a fractional ideal; it is the dual of I with respect to the trace, written Dual I. This is called a dual because Dual Dual I = I. It is easy to compute Dual I; see [2, section 4.8.4].

If J and I are both fractional ideals then J ÷ I is a fractional ideal. The operation (J, I) ↦ J ÷ I is called ideal division.

Lemma 8.1. If I and J are fractional ideals then J ÷ I = Dual(I Dual J).

Thus J ÷ I is easy to compute. It appears that this observation was first due to Peter Montgomery. My thanks to Hendrik W. Lenstra, Jr., for pointing out that this works in all orders, not just Dedekind domains. Lenstra also notes that J ∩ I = Dual(Dual J + Dual I), so intersection can be implemented in terms of addition (or vice versa).

Proof. In general A÷BC = (A÷B)÷C. Thus Dual(I Dual J) = T ÷(I Dual J) = (T ÷ Dual J) ÷ I = (Dual Dual J) ÷ I = J ÷ I. ⊓ ⊔

9 Ideals of non-equation orders

An order in a number field need not be of the form Z[x]/φ. The technique of lazy localization applies in tremendous generality; one can straightforwardly tensor the known computational universe with Z_{p}, or with completions of other convenient base rings. However, the ideal representation in section 5 is specific to Z_{p}[x]/φ, and it is not clear how to preserve the benefits of that representation in more general settings.

There is a very simple solution. If A is an order of Q(α) containing Z[α], where α is a root of φ, then any fractional ideal over A is—and can be represented as—a fractional ideal over Z[α]. In particular, I represent A itself as a fractional ideal over Z[α]; then I can compute a principal ideal βA by multiplying βZ[α] and A.

An alternate approach avoids fractional ideals. Say I is an ideal of A. One can multiply I by the discriminant of Z[α], or the different φ′(α), to obtain an ideal of Z[α].

References

1. Daniel J. Bernstein, Computing coprime bases in essentially linear time, preprint.

2. Henri Cohen, A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993.

3. Hideyuki Matsumura, Commutative ring theory, Cambridge University Press, Cambridge, 1986.

4. Michael E. Pohst, Computational algebraic number theory, Birkhaüser, Basel, 1993.

This article was processed by the author using the TEX macro package from Springer-Verlag.