Journal of Algorithms, to appear. Final revisions are in progress.

FACTORING INTO COPRIMES IN ESSENTIALLY LINEAR TIME

DANIEL J. BERNSTEIN

Abstract. Let S be a finite set of positive integers. A “coprime base for S” means a set P of positive integers such that (1) each element of P is coprime to every other element of P and (2) each element of S is a product of powers of elements of P. There is a natural coprime base for S. This paper introduces an algorithm that computes the natural coprime base for S in essentially linear time. The best previous result was a quadratic-time algorithm of Bach, Driscoll, and Shallit. This paper also shows how to factor S into elements of P in essentially linear time. The algorithms apply to any free commutative monoid with fast algorithms for multiplication, division, and greatest common divisors; e.g., monic polynomials over a field. They can be used as a substitute for prime factorization in many applications.

1. Introduction

It is not easy to factor integers into primes. The point of this paper is that it is easy to factor integers into coprimes.

Given a finite set S of positive integers, I can construct a set P, with any two distinct elements of P coprime, and factor every element of S into elements of P, in essentially linear time. The best previous result was a quadratic-time algorithm by Bach, Driscoll, and Shallit in [2]; see section 4 of this paper.

Similar comments apply to monic polynomials over a finite field. Here the Bach-Driscoll-Shallit algorithm has been superseded, at least in theory, by an algorithm of Kaltofen and Shoup in [16], which factors polynomials into primes in subquadratic expected time. I can factor a set of polynomials into coprimes in essentially linear time.

Applications. Coprimes are often an adequate substitute for primes. The following example is due to Hendrik W. Lenstra, Jr.: given positive integers a, b, c, one can compute a basis for the Z-module {(i, j, k) ∈ Z^{3} : a^{i}b^{j}c^{k} = 1} by first factoring a, b, c into coprimes and then doing linear algebra on the exponents in the factorizations. See [14] for a generalization.

Other applications, listed here in historical order: eliminating quantifiers (see [11]), converting any set of congruences to a set with coprime moduli (see [13, Remark 6.8] and [2, page 201]), finding the prime factors of n given the sum of n’s divisors (see [3]), computing in zero-dimensional rings by lazy localization (see [12] and [23, section 3.1]), lifting polynomial factorizations (see [15, section 3]), computing normal bases (see [18]), finding the maximal order in a number field by lazy factorization (see [19, section 4.6]), finding algebraic dependencies among radicals (see [21]), and performing arithmetic on ideals in a number field by lazy localization (see [5]).

Date: 19980108.

1991 Mathematics Subject Classification. Primary 11Y16.

The author was supported by the National Science Foundation under grant DMS–9600083.

Acknowledgments. Thanks to Igor Shparlinski for his comments.

Notation. {} is the empty set. #S is the cardinality of S. S − T, when S and T are sets, means all elements of S that are not in T. When a proposition appears inside brackets, it means 1 if the proposition is true, 0 otherwise; for example, [2 < 3] = 1.

2. Outline of the paper

This paper is organized into four parts.

Part I. Existence. Section 4 proves that one can construct a “coprime base” for any finite set S via division and greatest common divisors. The construction is the Bach-Driscoll-Shallit algorithm.

Section 6 establishes the useful concept of a “quasiprime.” Section 7 shows that there is only one coprime base that can be obtained from S via multiplication, division, and greatest common divisors: the “natural coprime base” for S, written cb S.

Rather than state every result twice, once for integers and once for polynomials, I have abstracted the algebraic properties that make the constructions work. The most general setting for the Bach-Driscoll-Shallit algorithm is a “Noetherian coid with cancellation,” defined in section 3. The most general setting for natural coprime bases, and for my algorithms, is a “free coid,” defined in section 5. Any free coid is Noetherian and has cancellation.

Readers not interested in maximum generality may skip sections 3 and 5. The semigroup of positive integers is a free coid; the semigroup of monic polynomials over a field is a free coid.

Part II. Two-element sets. Sections 10 through 13 give a series of constructions culminating in an algorithm, DCBA, to find the natural coprime base for any two-element set. Each construction takes essentially linear time, given essentiallylinear-time subroutines for multiplication, division, and gcd, as discussed in section 8. Motivation for DCBA appears in section 9.

Part III. Finite sets. Sections 14 through 18 give several further essentiallylinear-time constructions, culminating in an algorithm to find the natural coprime base for any finite set.

Part IV. Factorization. To factor a set S into coprimes, I first construct a coprime base P for S, and then factor S into elements of P. Sections 19 through 21 show how to carry out the factorization, given S and P, in essentially linear time.

Part I. Existence

3. Coids and maximal common divisors

A coid is a set with a commutative associative binary operation, written (a, b) ↦ ab, and a neutral element, written 1. Commutativity means ab = ba. Associativity means (ab)c = a(bc). Neutrality means 1a = a = a1.

When a = bq for some q, a is a multiple of b; a is divisible by b; b divides a; b is a divisor of a. If a divides b and b divides c then a divides c.

A coid H is Noetherian if any nonempty subset S ⊆ H has a minimal element. (Minimal means not divisible by any other elements of S; maximal means not dividing any other elements of S; maximum or greatest means divisible by all elements of S.)

In a Noetherian coid H one may apply Noetherian induction, which states that if T is a subset of H, and if T contains a whenever T contains all other divisors of a, then T = H. Indeed, H − T has no minimal element, so it must be empty.

A coid has cancellation if q = r whenever bq = br. In other words, when c is a multiple of b, there is a unique q such that c = bq; this q is denoted c/b.

Example. The set of nonsingular ideals in a Noetherian domain, under ideal multiplication, is a Noetherian coid with cancellation.

Theorem 3.1. Let B be a nonempty subset of a Noetherian coid with cancellation. Then there exists a maximal common divisor of B.

Here a common divisor of B means a divisor of every element of B.

Proof. Select b ∈ B. Define S = {b/d : d is a common divisor of B}. Observe that b ∈ S. Thus S has some minimal element, say b/g, where g is a common divisor of B. If g divides another common divisor d of B, then b/d divides b/g; but b/d ∈ S, so b/d = b/g by minimality of b/g, so d = g. Hence g is a maximal common divisor.

Theorem 3.2. Let a, b, g be elements of a Noetherian coid with cancellation. If g is a maximal common divisor of {a, b} then a/g is coprime to b/g.

Here c is coprime to d if the only common divisor of {c, d} is 1.

Proof. If d divides a/g and b/g then dg divides a and b. Certainly g divides dg, so by maximality g = dg, so d = 1 by cancellation.

Notes. The term “coid” is nonstandard. It may be viewed as an abbreviation of “commutative semigroup with identity” or as an abbreviation of “commutative monoid”; here semigroup means a set with an associative operation, and monoid means a semigroup with a neutral element. “Coid,” like “monoid,” should be pronounced to rhyme with “overjoyed.”

Under my definition of “Noetherian,” any Noetherian coid is combinatorial: a = b whenever a and b are associates (i.e., whenever a divides b and b divides a). One can systematically replace “equal” by “associate” and “minimal” by “minimal up to associates” and so on, obtaining definitions and results that apply to noncombinatorial coids. I prefer to avoid unnecessary complexity: given a general coid, one can simply consider the combinatorial coid of classes of associates.

“Coprime” is also known as “relatively prime.”

4. Coprime bases

A set P is coprime if each element of P is coprime to every other element of P. If P and Q are coprime sets, and each p ∈ P is coprime to each q ∈ Q, then P ∪ Q is a coprime set.

Let P and S be subsets of a Noetherian coid with cancellation. I call P a base for S if S is contained in the coid generated by P. If P is a base for S then P is a base for any subset of S.

P is a coprime base for S if P is coprime and P is a base for S.

Theorem 4.1. Let a, b be elements of a Noetherian coid with cancellation. Then there is a finite set P with an element d such that (1) P is a coprime base for {a, b};

(2) d divides b; (3) if p ∈ P − {d} then p divides a.

Proof. Apply Noetherian induction to ab—i.e., to the set of c such that the desired conclusion holds whenever ab = c.

Let g be a maximal common divisor of {a, b}. If g = 1 then the set {a, b} with element b satisfies the stated conditions. So assume that g ≠ 1; this implies that a ≠ 1 and b ≠ 1.

Consider (a/g)g, a divisor of ab; it is different from ab since b ≠ 1. By induction, there is a finite coprime base P for {a/g, g}, with an element d dividing g, and with all other elements dividing a/g.

Next consider d(b/g), a divisor of ab; it is different from ab since a ≠ 1. By induction, there is a finite coprime base Q for {d, b/g}, with an element e dividing b/g, and with all other elements dividing d.

Finally, consider R = (P − {d}) ∪ Q, with element e. (1) If p ∈ P − {d} and q ∈ Q then p and q are coprime. (Indeed, if q ≠ e then q divides d, so q is coprime to p, since P is a coprime set. If q = e then q divides b/g, but p divides a/g, so p and q are coprime by Theorem 3.2.) Hence R is a coprime set. (2) Since e divides b/g it also divides b. (3) Consider q ∈ R − {e}. If q ∈ P − {d} then q divides a/g, hence a. If q ∈ Q then q divides d, hence g, hence a.

Theorem 4.2. Let H be a Noetherian coid with cancellation. Let B be a finite coprime subset of H, and let a be an element of H. Then there is a finite set E such that (1) E is a coprime base for B ∪ {a}; (2) each element of E divides an element of B ∪ {a}.

Proof. Induct on the size of B. If B = {} then {a} satisfies (1) and (2). Otherwise pick b ∈ B. By Theorem 4.1, there is a finite coprime base P for {a, b}, with an element d dividing a, and with all other elements dividing b. Next, by induction, there is a finite set Q such that Q is a coprime base for (B − {b}) ∪ {d}, with every element of Q dividing an element of (B − {b}) ∪ {d}.

Finally, consider E = (P − {d}) ∪ Q. (1) If p ∈ P − {d} and q ∈ Q then p and q are coprime. (Indeed, if q divides d then p and q are coprime since P is a coprime set. If q does not divide d then it divides an element of B −{b}, but p divides b, so p and q are coprime since B is a coprime set.) Thus E is a coprime set. Furthermore, the coid generated by E contains d (via Q), hence all of P, hence a and b, hence all of B. So E is a coprime base for B ∪ {a}. (2) Consider q ∈ E. If q ∈ Q then q divides d, which divides a, or q divides an element of B − {b}. If q ∈ P − {d} then q divides b. Hence in any case q divides an element of B ∪ {a}.

Theorem 4.3. Let S be a finite subset of a Noetherian coid with cancellation. Then there is a finite coprime base for S.

Proof. Induct on the size of S. If S = {} then {} is a coprime base for S. Otherwise select a ∈ S. By induction, there is a finite coprime base B for S−{a}. By Theorem 4.2, there is a finite coprime base for B ∪ {a}, and hence for S.

Notes. The proof of Theorem 4.1 is an algorithm introduced by Bach, Driscoll, and Shallit in [2]. This algorithm is neither the first algorithm for constructing coprime bases (see [11]) nor the fastest (see section 9), but it is certainly the simplest. I call it the coprime base algorithm (CBA). Here is a C program that reads two small positive integers from its input and prints the CBA results:

   gcd(a,b) { return b ? gcd(b,a%b) : a; }
   cba(a,b) { int g = gcd(a,b);
     if (g == 1) { printf("%d ",a); return b; }
     return cba(cba(a/g,g),b/g); }
   main() { int a, b; scanf("%d %d",&a,&b);
     printf("%d\n",cba(a,b)); }

The proof of Theorem 4.2 is also an algorithm in [2]; I call it the coprime base extension algorithm (ECBA).

It is stated in [2] that Gaussian semigroups form a “suitable abstract setting” for these algorithms. (“Gaussian semigroup,” modulo associates, means free coid; see section 5.) Noetherian coids with cancellation are substantially more general.

Some authors say “P is pairwise coprime” instead of “P is coprime,” reserving “P is coprime” for the relatively unimportant concept that gcd P = 1.

5. Free coids and greatest common divisors

A free coid is a Noetherian coid with cancellation in which a is coprime to bc whenever a is coprime to both b and c.

Example. The nonzero ideals in a Dedekind domain form a free coid. Indeed, in a Dedekind domain, the sum of two ideals a and b is a common divisor of {a, b}, hence a maximal common divisor; if a + b = 1 and a + c = 1 then 1 = a + b(a + c) = a + ba + bc = a + bc by elementary ideal arithmetic.

Theorem 5.1. In a free coid, if a divides bc, with a coprime to b, then a divides c.

Proof. Let g be a maximal common divisor of {a, c}. By Theorem 3.2, a/g is coprime to c/g. By hypothesis a/g is coprime to b; so a/g is coprime to b(c/g) = bc/g. But a/g divides bc/g, so a/g must be 1. Thus a = g divides c.

Theorem 5.2. In a free coid, if x and y divide z, and h is a maximal common divisor of {x, y}, then xy/h divides z.

Proof. Write z = qy. Then x/h divides z/h = q(y/h). By Theorem 3.2, x/h and y/h are coprime. By Theorem 5.1, x/h divides q. Hence xy/h = (x/h)y divides qy = z.

Theorem 5.3. Let B be a nonempty subset of a free coid. Then there exists a greatest common divisor of B.

The greatest common divisor of B is denoted gcd B.

Proof. Let g be a maximal common divisor of B, and let d be any common divisor of B. Let h be a maximal common divisor of {g, d}. By Theorem 5.2, gd/h is a common divisor of B. But g is maximal, so g = gd/h, so d = h, so d divides g as claimed.

Notes. Theorem 5.1, in the case of the positive integers, is the fundamental theorem of arithmetic. It implies that factorizations into primes are unique; see Theorem 6.4. The reader may enjoy showing that every element of a Noetherian coid with cancellation has a factorization into irreducibles, and that irreducibles in free coids are primes; hence every element of a free coid has a unique factorization into primes. Thus a free coid is free in the usual sense. The converse is also true.

6. Quasiprimes and the ord function

Let p and a be elements of a free coid, with p ≠ 1. If a/p^{m} is coprime to p for some integer m ≥ 0 then p is a quasiprime for a. Observe that m is determined by p and a; it is denoted ord_{p} a.

If p is a quasiprime for every element of a set S then p is a quasiprime for S.

Theorem 6.1. Let a, b be elements of a free coid. If p is a quasiprime for {a, b} then p is a quasiprime for ab with ord_{p} ab = ord_{p} a + ord_{p} b.

Proof. By assumption a = up^{m} and b = vp^{n} where p is coprime to u and v. Then p is coprime to uv, so p is a quasiprime for ab = uvp^{m+n}, with ord_{p} ab = m + n = ord_{p} a + ord_{p} b.

Theorem 6.2. Let a, b be elements of a free coid. If p is a quasiprime for {a, ab} then p is a quasiprime for b.

Proof. By assumption a = up^{m} and ab = vp^{n} where p is coprime to u and v. Then p^{m} is coprime to v, and p^{m} divides vp^{n}, so p^{m} divides p^{n}, so m ≤ n. Next u divides vp^{n−m}, and u is coprime to p^{n−m}, so u divides v. Finally b = (v/u)p^{n−m}.

Theorem 6.3. Let a, b be elements of a free coid. Define g = gcd{a, b}. If p is a quasiprime for {a, b} then p is a quasiprime for g with ord_{p} g = min{ord_{p} a, ord_{p} b}.

Proof. By assumption a = up^{m} and b = vp^{n} where p is coprime to u and v. Without loss of generality assume m ≤ n. Since p^{m} is a common divisor of a and b, it divides g; write g = xp^{m}. Then x divides u, so p is coprime to x.

Theorem 6.4. Let P be a finite coprime subset of a free coid. Define a = ∏_{p∈P} p^{a_{p}} where each a_{p} is a nonnegative integer. Fix q ∈ P − {1}. Then q is a quasiprime for a, and ord_{q} a = a_{q}.

Hence factorizations into elements of P are unique if P is a finite coprime set not containing 1: the only factorization of a is ∏_{p∈P} p^{ord_{p} a}.

Proof. If p ∈ P, p ≠ q, then p is coprime to q by assumption, so ord_{q} p = 0. Also ord_{q} q = 1. By Theorem 6.1, ord_{q} ∏_{p} p^{a_{p}} = ∑_{p} a_{p} ord_{q} p = a_{q}.

Theorem 6.5. Let a, b be elements of a free coid H. Let S be a finite subset of H. If ord_{p} a = ord_{p} b whenever p is a quasiprime for S then a = b.

Proof. By Theorem 4.3, there is a finite coprime base P for S ∪ {a, b}. Write a = ∏_{p∈P} p^{a_{p}} and b = ∏_{p∈P} p^{b_{p}}. If p ∈ P − {1} then p is a quasiprime for S so a_{p} = ord_{p} a = ord_{p} b = b_{p} by Theorem 6.4. Hence a = b.

Theorem 6.6. Let a, b be elements of a free coid H. Let S be a finite subset of H. If ord_{p} a ≤ ord_{p} b whenever p is a quasiprime for S then a divides b.

Proof. Define g = gcd{a, b}. If p is a quasiprime for S then ord_{p} a ≤ ord_{p} b so ord_{p} g = ord_{p} a by Theorem 6.3. Hence g = a by Theorem 6.5.

Theorem 6.7. Let a, b be elements of a free coid H. Let S be a finite subset of H. If min{ord_{p} a, ord_{p} b} = 0 whenever p is a quasiprime for S then a is coprime to b.

Proof. Define g = gcd{a, b}. If p is a quasiprime for S then min{ord_{p} a, ord_{p} b} = 0 so ord_{p} g = 0 = ord_{p} 1 by Theorem 6.3. Hence g = 1 by Theorem 6.5.

7. The natural coprime base

Fix a subset S of a free coid. The natural coprime base for S, denoted cb S, is the set of maximal quasiprimes for S.

The coid generated by cb S is everything that can be constructed from S with multiplication, division, and greatest common divisors; see Theorem 7.5.

Theorem 7.1. Let S be a subset of a free coid. Let P be a coprime base for S, not containing 1, such that any quasiprime for S is a quasiprime for P. Then P = cb S.

Proof. Take p ∈ P. By Theorem 6.4, p is a quasiprime for S. Say p divides another quasiprime d for S. Then d is a quasiprime for p by assumption; since d and p are not coprime, d must divide p, so d = p. Hence p is maximal.

Conversely, let q be a maximal quasiprime for S. Then q divides some element of P. (If not, then q must be coprime to every element of P, since q is a quasiprime for P. Thus q is coprime to every element of S. But then q^{2} is a quasiprime for S, so q is not maximal.) Say q divides p ∈ P. By Theorem 6.4, p is a quasiprime for S, so by maximality q = p.

Theorem 7.2. Let S be a finite subset of a free coid. Then there is a finite coprime base P for S such that any quasiprime for S is a quasiprime for P.

Proof. According to Theorem 6.2 and Theorem 6.3, if p is a quasiprime for S, then p is a quasiprime for anything that can be created from S with division and gcd. The constructions in Theorems 4.1, 4.2, and 4.3 use solely division and gcd.

Theorem 7.3. Let S be a finite subset of a free coid. Then cb S is a finite coprime base for S. Furthermore, any quasiprime for S is a quasiprime for cb S.

Proof. By Theorem 7.2, there is a finite coprime base P for S such that any quasiprime for S is a quasiprime for P. Define Q = P − {1}; then Q is a coprime base for S, not containing 1, and any quasiprime for S is a quasiprime for Q. By Theorem 7.1, Q = cb S.

Theorem 7.4. Let Q be a coprime subset of a free coid. Then cb Q = Q − {1}.

Proof. Q − {1} is a coprime base for Q not containing 1. Any quasiprime for Q is certainly a quasiprime for Q − {1}. By Theorem 7.1, Q − {1} = cb Q.

Theorem 7.5. Let Q be a finite coprime subset of a free coid. Then Q is a base for {c} if and only if every quasiprime for Q is a quasiprime for c.

In particular, if Q is a base for {a, b}, then it is also a base for {ab, gcd{a, b}}, since any quasiprime for Q is a quasiprime for {ab, gcd{a, b}} by Theorem 6.4, Theorem 6.1, and Theorem 6.3. Similarly, if Q is a base for {a, ab} then it is also a base for {b}.

Proof. If Q is a base for {c} then every quasiprime for Q is a quasiprime for c by Theorem 6.4.

For the converse, define P = cb(Q ∪ {c}). Any quasiprime for Q is a quasiprime for Q ∪ {c} by assumption, hence for P. So P = cb Q by Theorem 7.1. Thus P = Q − {1} by Theorem 7.4. Since P is a base for {c}, Q is too.

Theorem 7.6. Let S be a finite subset of a free coid. Define P = cb S. If every element of S divides a then ∏_{p∈P} p divides a.

Proof. Take p ∈ P. If p does not divide any element of S then p is coprime to all elements of S so p^{2} is a quasiprime for S, contradicting the maximality of p. Thus p divides a. This is true for all p, so ∏_{p∈P} p divides a by Theorem 5.2.

Notes. My definition of the natural coprime base as the set of maximal quasiprimes is simpler than the characterizations in [15], [13, Remark 6.8], and [2, Theorem 3].

Part II. Two-element sets

8. Logarithms and M-time

Fix a free coid H. Fix a function lg : H → R such that (1) lg ab = lg a + lg b and (2) lg a ≥ 1 for any a ≠ 1. Observe that lg 1 = 0.

My algorithms use a black box that can multiply a and b, divide ab by b, check whether a divides b, or compute gcd{a, b} in time at most (1 + lg ab)μ(lg ab), where μ is a nondecreasing positive function. I write M-time for time spent inside this black box. I say that the black box supports fast arithmetic when μ(x) ∈ x^{o(1)}.

Examples. For the coid of positive integers, one may take lg a as the usual logarithm base 2. For the coid of monic polynomials over a field, one may take lg a as the degree of a. In each case there is an algorithm that achieves log μ(x) ∈ O(log log x).

Theorem 8.1. Let p, a be elements of a free coid. If p is a quasiprime for a then ord_{p} a ≤ lg a.

Proof. Put n = ord_{p} a. Then a = up^{n} for some u, so lg a = lg u + n lg p ≥ n.

Notes. See [20] for a fast gcd algorithm for integers. See [7] for a fast gcd algorithm for polynomials.

Subsequent sections use the above assumptions on lg and μ to bound the Mtime used by various algorithms. One can attach a lg function to any free coid by setting lg p = 1 for each prime p, and one can imagine a black box that performs each arithmetic operation in constant time. Conclusion: In any free coid, each algorithm terminates after finitely many arithmetic operations.

My M-time bounds are somewhat pessimistic in practice, for two reasons. First, one can actually divide ab by b in time depending only on the length of a. Second, multiplication, division, and divisibility testing are actually much faster than gcd. (This is also why I treat divisibility testing as a separate primitive, even though it could be implemented with gcd.)

9. From CBA to DCBA

The natural coprime base for {p^{e}, p^{f}} is {p^{g}} − {1} where g = gcd{e, f}. Thus natural coprime bases act on exponents as greatest common divisors.

Consider CBA, the algorithm described in section 4 for computing cb{a, b}. CBA replaces (a, b) with (a/gcd{a, b}, gcd{a, b}, b/gcd{a, b}); it focuses on the left pair in this triple and then on the right pair. If (a, b) = (p^{e}, p^{f}) then this triple is (p^{e−f}, p^{f}, 1) if e ≥ f or (1, p^{e}, p^{f−e}) if e ≤ f. Observe that the exponent pair (e, f) has been replaced with (e − f, f) or (e, f − e). Thus CBA uses Euclid’s subtractive algorithm to compute greatest common divisors of exponents.

Euclid’s subtractive algorithm is a dangerous way to compute greatest common divisors: the number of steps is the sum of the quotients in the continued fraction for e/f. A much safer alternative is Euclid’s repeated-division algorithm, where the number of steps is at worst logarithmic in e + f. Writing out the usual base-2 division algorithm inside Euclid’s algorithm produces “Brent’s left-shift binary gcd algorithm,” which replaces (e, f) with (e − 2^{k}f, f) for the largest possible value of k, or with (f, e) if e < f.

How DCBA operates on exponents. Define a function κ on pairs of nonnegative integers as follows:

κ(e, f) = {(f − e, e) if e ≤ f (e − f, f) if f < e ≤ 2f (e − 2f, f) if 2f < e ≤ 4f (e − 4f, f) if 4f < e ≤ 8f ⋮

Write κ^{i} for the ith iterate of κ. Define λ(a, b) as the smallest n ≥ 0 such that, for every quasiprime p for {a, b}, the second component of κ^{n}(ord_{p} a, ord_{p} b) is 0.

Theorem 9.1. If (e′, f′) = κ(e, f) then e′ + \sqrt{2}f′ ≤ (e + \sqrt{2}f)/\sqrt{2}.

Proof. If e ≤ f then \sqrt{2}e′ + 2f′ − e − \sqrt{2}f = (1 − \sqrt{2})e ≤ 0. Otherwise 2^{k}f < e ≤ 2^{k+1}f for some k ≥ 0, so \sqrt{2}e′ + 2f′ − e − \sqrt{2}f = (\sqrt{2} − 1)e − (2^{k}\sqrt{2} + \sqrt{2} − 2)f ≤ 2^{k+1}(\sqrt{2} − 1)f − (2^{k}\sqrt{2} + \sqrt{2} − 2)f = (1 − 2^{k})(2 − \sqrt{2})f ≤ 0.

Theorem 9.2. If n ≥ 0 and lg a + \sqrt{2} lg b < \sqrt{2}^{n+1} then λ(a, b) ≤ n.

Proof. Let p be a quasiprime for {a, b}. Define e = ord_{p} a, f = ord_{p} b, and (e′, f′) = κ^{n}(e, f). Then e′ + \sqrt{2}f′ ≤ (e + \sqrt{2}f)/\sqrt{2}^{n} < \sqrt{2} by Theorem 9.1, so f′ = 0.

Theorem 9.3. If λ(a, b) = 0 then b = 1.

Proof. If p is a quasiprime for {a, b} then ord_{p} b = 0 by definition of λ. By Theorem 6.5, b = 1.

Notes. See [17, sections 4.5.2 and 4.5.3] for a thorough discussion of Euclid’s subtractive gcd algorithm and Euclid’s repeated-division gcd algorithm.

10. Computing powers

Algorithm T. Given (a, n), with n a nonnegative integer, to print a^{2^{n}}: 1. If n = 0: Print a and stop.

2. Set a ← a^{2}. Set n ← n − 1. Return to step 1.

Theorem 10.1. Algorithm T computes a^{2^{n}} in M-time at most

(n + 2(2^{n} − 1) lg a)μ(2^{n} lg a).

Proof. For n = 0, Algorithm T uses no M-time, and n + 2(2^{n} − 1) lg a = 0. For n ≥ 1, Algorithm T first computes a^{2}, using M-time at most (1 + 2 lg a)μ(2 lg a) ≤ (1 + 2 lg a)μ(2^{n} lg a). It then computes (a^{2})^{2^{n−1}}, using M-time at most

(n − 1 + 2(2^{n−1} − 1) lg a^{2})μ(2^{n−1} lg a^{2}) = (n − 1 + 2(2^{n} − 2) lg a)μ(2^{n} lg a)

by induction. Finally 1 + 2 lg a + n − 1 + 2(2^{n} − 2) lg a = n + 2(2^{n} − 1) lg a.

Notes. Algorithm T is well known. For generalizations see [17, section 4.6.3].

11. The ppi, ppo, ppg, and pple functions

The defining properties of ppi(a, b), ppo(a, b), ppg(a, b), and pple(a, b) are that

ord_{p} ppi(a, b) = (ord_{p} a)[ord_{p} b > 0]
ord_{p} ppo(a, b) = (ord_{p} a)[ord_{p} b = 0]
ord_{p} ppg(a, b) = (ord_{p} a)[ord_{p} a > ord_{p} b]
ord_{p} pple(a, b) = (ord_{p} a)[ord_{p} a ≤ ord_{p} b]

whenever p is a quasiprime for both a and b. Constructive proofs of existence appear in Theorem 11.2 and Theorem 11.3 below. Uniqueness follows from Theorem 6.5.

Theorem 11.1. Let a, c, x_{0}, y_{0} be elements of a free coid, with x_{0}y_{0} = a and x_{0} = gcd{a, c}. For n ≥ 0 define g_{n+1} = gcd{x_{n}, y_{n}}, x_{n+1} = x_{n}g_{n+1}, and y_{n+1} = y_{n}/g_{n+1}. If p is a quasiprime for {a, c} then ord_{p} x_{n} = min{ord_{p} a, 2^{n} ord_{p} c}.

Note that x_{n}y_{n} = a.

Proof. Write e = ord_{p} a and f = ord_{p} c. Then ord_{p} x_{0} = min{e, f}.

Assume inductively that ord_{p} x_{n} = min{e, 2^{n}f}. If e < 2^{n}f then ord_{p} x_{n} = e so ord_{p} y_{n} = 0 so ord_{p} g_{n+1} = min{0, e} = 0; thus ord_{p} x_{n+1} = e = min{e, 2^{n+1}f}. If e ≥ 2^{n}f then ord_{p} x_{n} = 2^{n}f so ord_{p} y_{n} = e−2^{n}f so ord_{p} g_{n+1} = min{e − 2^{n}f, 2^{n}f}; thus ord_{p} x_{n+1} = 2^{n}f + min{e − 2^{n}f, 2^{n}f} = min{e, 2^{n+1}f}.

Theorem 11.2. Let a, c be elements of a free coid. Define x_{0} = gcd{a, c} and y_{0} = a/x_{0}. For n ≥ 0 define g_{n+1} = gcd{x_{n}, y_{n}}, x_{n+1} = x_{n}g_{n+1}, and y_{n+1} = y_{n}/g_{n+1}. If g_{n+1} = 1 then x_{n} = ppi(a, c) and y_{n} = ppo(a, c).

Proof. Select a quasiprime p for {a, c}; write e = ord_{p} a and f = ord_{p} c. If g_{n+1} = 1 then x_{n} = x_{n+1} so min{e, 2^{n}f} = min{e, 2^{n+1}f} by Theorem 11.1. If f = 0 then ord_{p} x_{n} = min{e, 0} = 0. If f > 0 then 2^{n}f < 2^{n+1}f so e ≤ 2^{n}f; thus ord_{p} x_{n} = e. Hence in general ord_{p} x_{n} = e[f > 0] and ord_{p} y_{n} = e − ord_{p} x_{n} = e[f = 0].

Theorem 11.3. Let a, b be elements of a free coid. Define y_{0} = gcd{a, b} and x_{0} = a/y_{0}. For n ≥ 0 define g_{n+1} = gcd{x_{n}, y_{n}}, x_{n+1} = x_{n}g_{n+1}, and y_{n+1} = y_{n}/g_{n+1}. If g_{n+1} = 1 then x_{n} = ppg(a, b) and y_{n} = pple(a, b).

Proof. Define c = x_{0}. Then x_{n} = ppi(a, c) and y_{n} = ppo(a, c) by Theorem 11.2. Select a quasiprime p for {a, b}; write e = ord_{p} a and f = ord_{p} b. Then ord_{p} y_{0} = min{e, f}, so ord_{p} c is 0 exactly when e ≤ f. Thus ord_{p} x_{n} = e[ord_{p} c > 0] = e[e > f] and ord_{p} y_{n} = e[ord_{p} c = 0] = e[e ≤ f].

Theorem 11.4. In the situation of Theorem 11.1, if k ≥ 0 and 2^{k} ≥ lg a then g_{k+1} = 1.

Proof. Say p is a quasiprime for {a, c}. By Theorem 8.1, ord_{p} a ≤ lg a. By Theorem 11.1, ord_{p} x_{k} = min{ord_{p} a, 2^{k} ord_{p} c}. If ord_{p} c = 0 then ord_{p} x_{k} = 0 = ord_{p} x_{k+1}. If ord_{p} c > 0 then 2^{k} ord_{p} c ≥ 2^{k} ≥ lg a ≥ ord_{p} a so ord_{p} x_{k} = ord_{p} a = ord_{p} x_{k+1}. Hence ord_{p} g_{k+1} = ord_{p} x_{k+1} − ord_{p} x_{k} = 0. This is true for all p, so g_{k+1} = 1.

The following two algorithms include n solely for expository purposes. Algorithm PPIO. Given (a, c), to print gcd{a, c}, ppi(a, c), and ppo(a, c):

1. Set x ← gcd{a, c}. Print x. Set y ← a/x. Set n ← 0.

2. (Now (x, y) = (x_{n}, y_{n}) in Theorem 11.2.) Set g ← gcd{x, y}. If g = 1: print x, print y, and stop.

3. Set x ← xg and y ← y/g. Set n ← n + 1. Return to step 2. Algorithm PPGLE. Given (a, b), to print gcd{a, b}, ppg(a, b), and pple(a, b):

1. Set y ← gcd{a, b}. Print y. Set x ← a/y. Set n ← 0.

2. (Now (x, y) = (x_{n}, y_{n}) in Theorem 11.3.) Set g ← gcd{x, y}. If g = 1: print x, print y, and stop.

3. Set x ← xg and y ← y/g. Set n ← n + 1. Return to step 2.

Theorem 11.5. Let a, c be elements of a free coid. Algorithm PPIO computes (gcd, ppi, ppo)(a, c) in M-time at most (3k + 3 + (2k + 4) lg a + lg c)μ(lg ac) if k ≥ 0 and 2^{k} ≥ lg a.

Proof. By Theorem 11.4, g_{k+1} = 1, so the algorithm stops when n = k if not earlier. It thus performs step 2 for n ∈ {0, 1, …, k} at most, and step 3 for n ∈ {0, 1, …, k − 1} at most.

Step 1 uses M-time at most (1 + lg ac)μ(lg ac) to compute gcd{a, c} and M-time at most (1 + lg a)μ(lg a) to compute a/x.

Each iteration of step 2 uses M-time at most (1 + lg a)μ(lg a) since xy = x_{n}y_{n} = a. The total is at most (k + 1)(1 + lg a)μ(lg a).

An iteration of step 3 uses M-time at most (1+lg xg)μ(lg xg)+(1+lg y)μ(lg y) ≤ (2 + lg x_{n+1} + lg y_{n})μ(lg a). The total for n ∈ {0, 1, 2, …, k − 1} telescopes to (2k + lg x_{k} + (k − 1) lg a + lg y_{0})μ(lg a), which is at most (2k + (k + 1) lg a)μ(lg a).

Add: (1 + lg ac) + (1 + lg a) + (k + 1)(1 + lg a) + (2k + (k + 1) lg a) = 3k + 3 + (2k + 4) lg a + lg c.

Theorem 11.6. Let a, b be elements of a free coid. Algorithm PPGLE computes (gcd, ppg, pple)(a, b) in M-time at most (3k +3+(2k +4) lg a+lg b)μ(lg ab) if k ≥ 0 and 2^{k} ≥ lg a.

Proof. Same analysis as in Theorem 11.5.

Notes. The ppo function is the subject of [18]. Write r = ppo(a, b). Then r is a divisor of a, coprime to b, such that each quasiprime for {a, b} dividing a/r also divides b. Lüneburg’s algorithm in [18] takes quadratic time on inputs (p^{n}, p).

The ppg function is the subject of [22, section 19]. Write A = ppg(a, b) and B = b/gcd{A, b}. Then A divides a, and B divides b; A and B are coprime; and AB is the least common multiple of a and b. Stieltjes’s algorithm in [22] takes quadratic time on inputs (p^{n+1}, p^{n}).

The notation ppi(a, b) stands for “powers in a of primes inside b”; ppo(a, b) is “powers in a of primes outside b”; ppg(a, b) is “prime powers in a greater than those in b”; and pple(a, b) is “prime powers in a less than or equal to those in b.”

12. The ls function

Fix a, b in a free coid. Define ls_{n}(a, b) as the triple (g_{n}, h_{n}, c_{n}), where (g_{0}, h_{0}, c_{0}) = (gcd, ppg, pple)(ppi(a, b), b) and (g_{n+1}, h_{n+1}, c_{n+1}) = (gcd, ppg, pple)(h_{n}, g_{n}^{2}).

Theorem 12.1. Let a, b be elements of a free coid. Let p be a quasiprime for {a, b}. Define e = ord_{p} a and f = ord_{p} b. Define (g_{n}, h_{n}, c_{n}) = ls_{n}(a, b). Then (ord_{p} g_{n}, ord_{p} h_{n}, ord_{p} c_{n}) = [0 < 2^{n−1}f < e](min{e, 2^{n}f}, e[e > 2^{n}f], e[e ≤ 2^{n}f]) for n ≥ 1.

Proof. Notice that ord_{p} g_{n+1}, ord_{p} h_{n+1}, and ord_{p} c_{n+1} are all bounded by ord_{p} h_{n}. Therefore if ord_{p} h_{m} = 0 then ord_{p} g_{n} = ord_{p} h_{n} = ord_{p} c_{n} = 0 for all n > m.

Case 1: f = 0. Then ord_{p} ppi(a, b) = 0 so ord_{p} g_{n} = ord_{p} h_{n} = ord_{p} c_{n} = 0 for all n.

Case 2: e ≤ f. Then ord_{p} ppi(a, b) = e, so ord_{p} h_{0} = e[e > f] = 0, so ord_{p} g_{n} = ord_{p} h_{n} = ord_{p} c_{n} = 0 for all n ≥ 1.

Case 3: e > f > 0. Then ord_{p} ppi(a, b) = e, so ord_{p} h_{0} = e and ord_{p} g_{0} = f. Thus ord_{p} g_{1} = min{e, 2f}; ord_{p} h_{1} = e[e > 2f]; and ord_{p} c_{1} = e[e ≤ 2f].

Assume inductively ord_{p} g_{n} = [2^{n−1}f < e] min{e, 2^{n}f} and ord_{p} h_{n} = e[e > 2^{n}f]. If e ≤ 2^{n}f then ord_{p} h_{n} = 0 so ord_{p} g_{n+1} = ord_{p} h_{n+1} = ord_{p} c_{n+1} = 0 as desired. If e > 2^{n}f then (ord_{p} g_{n}, ord_{p} h_{n}) = (2^{n}f, e) so ord_{p} g_{n+1} = min{e, 2^{n+1}f} as desired; ord_{p} h_{n+1} = e[e > 2^{n+1}f] as desired; and ord_{p} c_{n+1} = e[e ≤ 2^{n+1}f] as desired.

Theorem 12.2. Let a, b be elements of a free coid. Define (g_{n}, h_{n}, c_{n}) = ls_{n}(a, b). If m ≥ 1 and h_{m} = 1 then a = c_{0}c_{1} … c_{m} ppo(a, b). Furthermore, any two members of the sequence c_{0}, c_{1}, …, c_{m}, ppo(a, b) are coprime.

Proof. Let p be a quasiprime for {a, b}. Write e = ord_{p} a and f = ord_{p} b. I will show that the sum of the numbers ord_{p} c_{0}, ord_{p} c_{1}, …, ord_{p} c_{m}, ord_{p} ppo(a, b) is e, and that at most one of the numbers is nonzero.

Case 1: f = 0. Then ord_{p} ppi(a, b) = 0 so ord_{p} c_{0} = 0; ord_{p} c_{n} = 0 for n ≥ 1; and ord_{p} ppo(a, b) = e.

Case 2: e ≤ f. Then ord_{p} ppo(a, b) = 0; ord_{p} c_{0} = e[e ≤ f] = e; and ord_{p} c_{n} = 0 for n ≥ 1.

Case 3: e > f > 0. Then ord_{p} ppo(a, b) = 0; ord_{p} c_{0} = 0; and ord_{p} c_{n} = e[2^{n−1}f < e ≤ 2^{n}f] for n ≥ 1. There is exactly one value of k ≥ 1 for which 2^{k−1}f < e ≤ 2^{k}f. Furthermore ord_{p} h_{m} = 0 so e ≤ 2^{m}f so k ≤ m.

Theorem 12.3. Let a, b be elements of a free coid. Define (g_{n}, h_{n}, c_{n}) = ls_{n}(a, b). Define d_{n} = gcd{c_{n}, b} for n ≥ 1. Then d_{n}^{2^{n−1}} divides c_{n}. Furthermore, if m ≥ 1 and h_{m} = 1, then c_{0}d_{1}d_{2} … d_{m} divides b, and b/d_{1}d_{2} … d_{m} is coprime to a/c_{0}.

Proof. Let p be a quasiprime for {a, b}. Write e = ord_{p} a and f = ord_{p} b. Then ord_{p} c_{n} = e[2^{n−1}f < e ≤ 2^{n}f] by Theorem 12.1, so ord_{p} d_{n} = f[2^{n−1}f < e ≤ 2^{n}f], so 2^{n−1} ord_{p} d_{n} ≤ e[2^{n−1}f < e ≤ 2^{n}f] = ord_{p} c_{n}. Thus d_{n}^{2^{n−1}} divides c_{n}.

Next, ord_{p} d_{1}d_{2} … d_{m} = f[f < e ≤ 2^{m}f], and ord_{p} c_{0} = e[e ≤ f] ≤ f[e ≤ f], so ord_{p} c_{0}d_{1}d_{2} … d_{m} ≤ f[e ≤ 2^{m}f] ≤ f. Thus c_{0}d_{1}d_{2} … d_{m} divides b.

If h_{m} = 1 then f = 0 or e ≤ 2^{m}f. Either way ord_{p} d_{1}d_{2} … d_{m} = f[f < e], so ord_{p}(b/d_{1}d_{2} … d_{m}) = f[e ≤ f]. On the other hand ord_{p}(a/c_{0}) = e[e > f]. Thus b/d_{1}d_{2} … d_{m} and a/c_{0} are coprime.

Notes. The name ls stands for “left shift.” This function splits up the quasiprimes in a according to the cases in the definition of κ in section 9.

13. Computing a coprime base for a two-element set

This section introduces a fast algorithm, DCBA, to compute the natural coprime base for {a, b}. For the correctness of DCBA, see Theorem 13.1. For speed, see Theorem 13.3.

Theorem 13.1. Let a, b be elements of a free coid. Define (g_{n}, h_{n}, c_{n}) = ls_{n}(a, b). Define d_{n} = gcd{c_{n}, b} for n ≥ 1. Assume that h_{m} = 1 with m ≥ 1. Define P_{n} = cb{c_{n}/d_{n}^{2^{n−1}}, d_{n}} for 1 ≤ n ≤ m. Define Q = cb{b/c_{0}d_{1}d_{2} … d_{m}, c_{0}}. Define R = cb{ppo(a, b)}. Then P = ⋃ P_{n} is a disjoint union; P ∪ Q ∪ R is a disjoint union; and P ∪ Q ∪ R = cb{a, b}.

Proof. By construction d_{n} divides c_{n}, so each element of P_{n} divides c_{n}. Hence, by Theorem 12.2, elements of P_{n} are coprime to elements of P_{k} for k ≠ n. Natural coprime bases do not contain 1, so P_{1}, P_{2}, …, P_{m} are disjoint, and their union P is a coprime set.

Next, by Theorem 12.2 again, c_{1}, c_{2}, …, c_{m} are coprime to ppo(a, b), so P is disjoint from R, and P ∪ R is a coprime set.

Next, each element of Q divides b/d_{1}d_{2} … d_{m}, hence is coprime to a/c_{0} = c_{1}c_{2} … c_{m} ppo(a, b) by Theorem 12.3 and Theorem 12.2. Thus Q is disjoint from P ∪ R, and P ∪ Q ∪ R is a coprime set.

Next, the coid generated by P ∪ Q ∪ R contains b/c_{0}d_{1}d_{2} … d_{m} (via Q), c_{0} (via Q), and each d_{n} (via P_{n}), so it contains b. It also contains c_{n}/d_{n}^{2^{n−1}} and thus c_{n} (via P_{n}), as well as ppo(a, b) (via R), so it contains c_{0}c_{1} … c_{m} ppo(a, b) = a by Theorem 12.2.

Finally, naturalness follows from Theorem 7.1.

Algorithm DCB (DCBA). Given (a, b), to print cb{a, b}:

1. If b = 1: Print a if a ≠ 1. Stop.

2. Compute (a, r) ← (ppi, ppo)(a, b) by Algorithm PPIO.

3. Print r if r ≠ 1.

4. Compute (g, h, c) ← (gcd, ppg, pple)(a, b) by Algorithm PPGLE.

5. Set c_{0} ← c. Set x ← c_{0}.

6. Set n ← 1.

7. Compute (g, h, c) ← (gcd, ppg, pple)(h, g^{2}) by Algorithm PPGLE.

8. Set d ← gcd{c, b}.

9. (Now (g, h, c, d) = (g_{n}, h_{n}, c_{n}, d_{n}).) Set x ← xd.

10. Compute y ← d^{2^{n−1}} by Algorithm T.

11. Recursively apply DCBA to (c/y, d).

12. If h ≠ 1: Set n ← n + 1. Return to step 7.

13. Recursively apply DCBA to (b/x, c_{0}).

Beware that the order of arguments is important in DCBA’s recursive calls.

Theorem 13.2. Let a, b be elements of a free coid. Define (g_{n}, h_{n}, c_{n}) = ls_{n}(a, b). If m ≥ 1 and 2^{m−1} ≥ lg a then h_{m} = 1.

Proof. Say p is a quasiprime for {a, b}. Write e = ord_{p} a and f = ord_{p} b. Then e ≤ lg a ≤ 2^{m−1} by Theorem 8.1. If f = 0 then ord_{p} h_{m} = 0; if f ≥ 1 then e ≤ 2^{m−1}f so again ord_{p} h_{m} = 0.

Theorem 13.3. Let a, b be elements of a free coid. If m ≥ 1 and 2^{m−1} ≥ lg ab then DCBA finishes in M-time at most λ(a, b)(4m^{2} + 12m + 4)(lg ab)μ(3 lg ab).

Proof. If b = 1 then DCBA stops immediately, using no M-time. Otherwise λ(a, b) ≥ 1 by Theorem 9.3.

The point here is that λ(a, b) decreases at each level of the recursion: λ(c/y, d) ≤ λ(a, b) − 1 in step 11, and λ(b/x, c_{0}) ≤ λ(a, b) − 1 in step 13. Indeed, let p be a quasiprime for {a, b}. Write e = ord_{p} a and f = ord_{p} b. Then the pair (ord_{p}(c_{n}/d_{n}^{2^{n−1}}), ord_{p} d_{n}) is (e − 2^{n−1}f, f) = κ(e, f) if 2^{n−1}f < e ≤ 2^{n}f, (0, 0) otherwise. The pair (ord_{p}(b/c_{0}d_{1}d_{2} … d_{m}), ord_{p} c_{0}) is (f − e, e) = κ(e, f) if e ≤ f, (0, 0) otherwise.

So induct on λ(a, b). The product of the inputs to DCBA in step 11 and step 13 is b ∏_{n≥1}(c_{n}/d_{n}^{2^{n−1}}), which divides ab by Theorem 12.2. By induction, all the recursive calls together use M-time at most (λ(a, b) − 1)(4m^{2} + 12m + 4)(lg ab)μ(3 lg ab). It therefore suffices to prove that the non-recursive work in DCBA takes M-time at most (4m^{2} + 12m + 4)(lg ab)μ(3 lg ab).

Step 2 and step 4 each use M-time at most (3m + (2m + 2) lg a + lg b)μ(lg ab) by Theorem 11.5 and Theorem 11.6 respectively. The division in step 13 uses M-time at most (1 + lg b)μ(lg b).

Steps 7 through 12 are performed for n ∈ {1, 2, …, m} at most, since h_{m} = 1 by Theorem 13.2. Step 7 uses M-time at most (3m + (2m + 2) lg h + lg g^{2})μ(lg hg^{2}) ≤ (3m + (2m + 4) lg a)μ(lg a^{3}) per iteration by Theorem 11.5 since h and g divide a.

Step 8 uses M-time at most (1 + lg ab)μ(lg ab) per iteration since c divides a. Step 9 uses M-time at most (1 + lg b)μ(lg b) per iteration since the final value of

x divides b.

By Theorem 10.1, step 10 uses M-time at most (n−1+(2^{n}−2) lg d)μ(2^{n−1} lg d) ≤ (m − 1 + 2 lg a)μ(lg a) per iteration.

Finally, the division in step 11 uses M-time at most (1+lg a)μ(lg a) per iteration. The total is at most μ(lg a^{3}b) times 4m^{2} + 8m + 1 + (2m^{2} + 12m + 4) lg a +

(2m + 3) lg b, which is at most (2m^{2} + 12m + 4) lg a + (4m^{2} + 10m + 4) lg b ≤ (4m^{2} + 12m + 4) lg ab since lg b ≥ 1.

Theorem 13.4. Let a, b be elements of a free coid. If m ≥ 1 and 2^{m−1} ≥ lg ab then DCBA finishes in M-time at most 8m(m^{2} + 3m + 1)(lg ab)μ(3 lg ab).

Proof. By Theorem 9.2, λ(a, b) ≤ 2m.

Notes. Although DCBA is much faster than CBA in the worst case, CBA is faster on average for many input distributions. In practice one should start with CBA, switching to DCBA after a few steps.

Part III. Finite sets

14. The prod function

For any finite set S define prod S = ∏_{a∈S} a. The following algorithm computes prod S by binary splitting: Algorithm P. Given a finite set S, to print prod S:

1. If S = {}: Print 1. Stop.

2. If #S = 1: Find a ∈ S. Print a. Stop.

3. Select T ⊆ S with #T = ⌊#S/2⌋.

4. Compute X ← prod T by Algorithm P recursively.

5. Compute Y ← prod(S − T) by Algorithm P recursively.

6. Print XY.

Theorem 14.1. Let S be a finite subset of a free coid. If 2^{m} ≥ #S ≥ 1 then Algorithm P computes prod S in M-time at most (#S−1+m lg prod S)μ(lg prod S).

Proof. Induct on m.

Case 1: #S = 1. Algorithm P uses no M-time; and #S − 1 + m lg prod S ≥ 0. Case 2: #S ≥ 2. Then m ≥ 1. In Algorithm P, #T = ⌊#S/2⌋, so #T ≤ 2^{m−1}

and #(S − T) ≤ 2^{m−1}. In steps 4 and 5, by induction, Algorithm P uses M-time at most

(#T − 1 + (m − 1) lg prod T)μ(lg prod T)
+ (#(S − T) − 1 + (m − 1) lg prod(S − T))μ(lg prod(S − T))
≤ (#S − 2 + (m − 1) lg prod S)μ(lg prod S)

since lg prod T +lg prod(S −T) = lg prod S. In step 6, Algorithm P uses M-time at most (1 + lg prod S)μ(lg prod S). Add: #S − 2 + (m − 1) lg prod S + 1 + lg prod S = #S − 1 + m lg prod S.

Notes. Algorithm P is well known; it appears in, e.g., [6, exercise 6.4–10(a)].

15. The split function

For any coprime set P define split(a, P) = {(p, ppi(a, p)) : p ∈ P }. Algorithm S below computes split(a, P).

Theorem 15.1. Let b be an element of a free coid H. Let P be a finite coprime subset of H. Then b = ppo(b, prod P) ∏_{p∈P} ppi(b, p).

Proof. Let q be a quasiprime for P ∪ {b}. I will show that ord_{q} b = ord_{q} ppo(b, x) + ∑_{p∈P} ord_{q} ppi(b, p) where x = prod P.

Case 1: q divides some p ∈ P. Then ord_{q} x > 0 so ord_{q} ppo(b, x) = 0, and ord_{q} p > 0 so ord_{q} ppi(b, p) = ord_{q} b. If p′ ∈ P with p′ ≠ p then p′ is coprime to p by assumption, so ord_{q} p′ = 0, so ord_{q} ppi(b, p′) = 0.

Case 2: q does not divide any p ∈ P. Then ord_{q} p = 0 so ord_{q} ppi(b, p) = 0. Also ord_{q} x = 0, so ord_{q} ppo(b, x) = ord_{q} b.

Theorem 15.2. Let a, x, y be elements of a free coid. Set b = ppi(a, xy). Then ppi(b, x) = ppi(a, x).

Proof. Let p be a quasiprime for {a, x, y}, and write e = ord_{p} a. Then ord_{p} b = e[ord_{p} xy > 0], so ord_{p} ppi(b, x) = e[ord_{p} xy > 0][ord_{p} x > 0] = e[ord_{p} x > 0] = ord_{p} ppi(a, x).

Theorem 15.3. Let a be an element of a free coid H. Let P be a finite subset of H. Define b = ppi(a, prod P). Then split(a, P) = split(b, P).

Proof. If p ∈ P then p divides prod P so ppi(b, p) = ppi(a, p) by Theorem 15.2.

Algorithm S. Given (a, P), to print split(a, P):

1. If P = {}: Stop.

2. Compute b ← ppi(a, prod P).

3. If #P = 1: find p ∈ P, print (p, b), and stop.

4. Select Q ⊆ P with #Q = ⌊#P/2⌋.

5. Print split(b, Q) by Algorithm S recursively.

6. Print split(b, P − Q) by Algorithm S recursively.

Theorem 15.4. Let a be an element of a free coid H. Let P be a finite coprime subset of H. Define x = prod P and b = ppi(a, x). Then Algorithm S computes split(a, P) in M-time at most

(2k + 4)(lg a + 2m lg b) + \frac{(m + 1)(m + 2)}{2} lg x + (m + 5 + 6k)#P − 3k − 2

times μ(lg ax) if k ≥ 0, 2^{k} ≥ lg a, and 2^{m} ≥ #P ≥ 1.

Proof. Induct on m. Write y = prod Q and z = prod(P − Q). Then y and z are coprime since P is coprime, so lg ppi(b, y) + lg ppi(b, z) ≤ lg b by Theorem 15.1.

Algorithm S spends M-time at most (#P − 1 + m lg x)μ(lg x) computing prod P by Theorem 14.1, and M-time at most (3k+3+(2k+4) lg a+lg x)μ(lg ax) computing b by Theorem 11.5.

Case 1: #P = 1. Then Algorithm S stops in step 3. The total M-time is at most μ(lg ax) times

3k+3+(2k+4) lg a+lg x ≤ (2k+4)(lg a+2m lg b)+ \frac{(m + 1)(m + 2)}{2} lg x+m+3+3k

as claimed.

Case 2: #P ≥ 2. Then Algorithm S performs two recursive calls. By induction the first uses M-time at most

(2k + 4)(lg b + 2(m − 1) lg ppi(b, y)) + \frac{m(m + 1)}{2} lg y + (m + 4 + 6k)#Q − 3k − 2

times μ(lg by) and the second uses M-time at most

(2k +4)(lg b+2(m−1) lg ppi(b, z))+ \frac{m(m + 1)}{2} lg z +(m+4+6k)#(P −Q)−3k −2

times μ(lg bz). Thus the total M-time is at most μ(lg ax) times

(#P − 1 + m lg x) + (3k + 3 + (2k + 4) lg a + lg x)

+ (2k + 4)(2 lg b + 2(m − 1) lg b) + \frac{m(m + 1)}{2} lg x + (m + 4 + 6k)#P − 6k − 4,

which equals the claimed bound.

Notes. There is some redundancy in Algorithm S. Step 5 and step 6 recursively calculate products of various subsets of P; so does step 2. One could save time by storing products in step 2 for later use.

16. Extending a coprime base

Given a coprime set P, EDCBA below finds the natural coprime base for P ∪{b}.

Theorem 16.1. Let b be an element of a free coid H. Let P be a finite coprime subset of H. Define x = prod P. For each p ∈ P define Q_{p} = cb{p, ppi(b, p)}. Define R = cb{ppo(b, x)}. Then Q = ⋃ Q_{p} is a disjoint union; Q ∪ R is a disjoint union; and Q ∪ R = cb(P ∪ {b}).

Proof. If p and p′ are distinct elements of P then p and p′ are coprime so ppi(b, p) and ppi(b, p′) are coprime. Thus Q_{p} and Q_{p′} are disjoint, and Q is a coprime set.

If p ∈ P then p divides x so both p and ppi(b, p) are coprime to ppo(b, x). Thus Q and R are disjoint, and Q ∪ R is a coprime set.

The coid generated by Q ∪ R contains each p ∈ P (via Q_{p}). It also contains each ppi(b, p) and ppo(b, x), hence b by Theorem 15.1.

Naturalness follows from Theorem 7.1.

Algorithm EDCB (EDCBA). Given (P, b), P coprime, to print cb(P ∪ {b}): 1. Compute x ← prod P by Algorithm P.

2. Compute (a, r) ← (ppi, ppo)(b, x) by Algorithm PPIO.

3. Print r if r ≠ 1.

4. Compute S ← split(a, P) by Algorithm S.

5. For each (p, c) ∈ S: Apply DCBA to (p, c).

Theorem 16.2. Let b be an element of a free coid H. Let P be a nonempty finite coprime subset of H. Define x = prod P. EDCBA finishes in M-time at most 7m#P + (8m^{3} + 28m^{2} + 16m + 4) lg b + (8m^{3} + 24.5m^{2} + 10.5m + 2) lg x times μ(3 lg bx) if m ≥ 1 and 2^{m−1} ≥ lg bx.

A simpler bound when 1 ∉ P is (8m^{3} + 28m^{2} + 18m + 4)(lg bx)μ(3 lg bx).

Proof. Note that #P ≤ 1 + lg x ≤ 1 + 2^{m−1} ≤ 2^{m}.

Step 1 takes M-time at most (#P − 1 + m lg x)μ(lg x) by Theorem 14.1. Step 2 takes M-time at most (3m+(2m+2) lg b+lg x)μ(lg bx) by Theorem 11.5. Step 4 takes M-time at most (2m + 2)(2m + 1) lg b + (1/2)(m + 1)(m + 2) lg x +

(7m − 1)#P − 3m + 1 times μ(lg bx) by Theorem 15.4.

By Theorem 13.4, the application of DCBA to (p, c) in step 5 takes M-time at most 8m(m^{2} + 3m + 1)(lg cp)μ(3 lg cp). The sum of lg cp is at most lg bx, since the product of c’s divides b by Theorem 15.1.

17. Merging coprime bases

Algorithm U below finds cb(P ∪ Q) if P is coprime and Q is coprime. Let k be a nonnegative integer. I define bit_{i} k as the ith bit in k’s binary

expansion; thus k = ∑_{i≥0} 2^{i} bit_{i} k, with bit_{i} k ∈ {0, 1}.

Theorem 17.1. Let q_{0}, q_{1}, …, q_{n−1} be elements of a free coid, with q_{j} coprime to q_{k} for j ≠ k. Let b ≥ 1 be an integer such that 2^{b} ≥ n. Define x(e, i) = prod{q_{k} : bit_{i} k = e}. Then a coprime set P is a base for {q_{0}, …, q_{n−1}} if and only if it is a base for {x(0, 0), x(0, 1), …, x(0, b − 1), x(1, 0), x(1, 1), …, x(1, b − 1)}.

Proof. The point is that q_{k} = gcd{x(bit_{i} k, i) : 0 ≤ i < b}. Indeed, the gcd is a product of q’s by Theorem 7.5. It is divisible by q_{j} if and only if q_{j} divides each x(bit_{i} k, i), i.e., bit_{i} j = bit_{i} k for each i, i.e., j = k.

Now if P is a base for all x(e, i) then P is a base for gcd{x(bit_{i} k, i) : 0 ≤ i < b} = q_{k} by Theorem 7.5.

Conversely, if P is a base for all the q’s then it is also a base for the x’s, since each x(e, i) is a product of q’s.

Algorithm U. Given (P, Q), with P coprime and Q coprime, to print cb(P ∪ Q): 1. Set n = #Q. Label the elements of Q as q_{0}, q_{1}, …, q_{n−1}.

2. Find the smallest b ≥ 1 with 2^{b} ≥ n. Set S ← P. Set i ← 0.

3. If i ≥ b: Print S. Stop.

4. Compute x ← prod{q_{k} : bit_{i} k = 0} by Algorithm P.

5. Compute T ← cb(S ∪ {x}) by EDCBA.

6. Compute x ← prod{q_{k} : bit_{i} k = 1} by Algorithm P.

7. Compute S ← cb(T ∪ {x}) by EDCBA.

8. Set i ← i + 1. Return to step 3.

Theorem 17.2. Let P and Q be finite coprime subsets of a free coid. Then Algorithm U prints cb(P ∪ Q).

Proof. Apply Theorem 17.1. The set S printed by Algorithm U is a coprime base for P ∪ {x(0, 0), x(0, 1), …, x(0, b − 1), x(1, 0), x(1, 1), …, x(1, b − 1)} by construction, and therefore a coprime base for P ∪ Q. Naturalness follows from Theorem 7.1.

Theorem 17.3. Let P and Q be finite coprime subsets of a free coid, with 1 ∉ P ∪ Q. Define z = (prod P)(prod Q)^{2}. If m ≥ 1 and 2^{m−1} ≥ lg z then Algorithm U finishes in M-time at most 2m(8m^{3} + 28m^{2} + 19m + 4)(lg z)μ(3 lg z).

Proof. By Theorem 7.6, prod S always divides (prod P)(prod Q); and x divides prod Q. Thus step 5 uses M-time at most (8m^{3} + 28m^{2} + 18m + 4)(lg z)μ(3 lg z) per iteration by Theorem 16.2. Step 4 uses M-time at most m(lg z)μ(lg z) by Theorem 14.1. Similar comments apply to step 7 and step 6.

Notes. Theorem 17.1 is crucial to my improvement over [2]. One can simply apply EDCBA to each element of Q in turn, as in Theorem 4.3, but this is far too slow when #Q is large. The trick here is to replace Q with a new set that has far fewer elements but has Q as its natural coprime base. One disadvantage of this trick is that the new set takes b times as much space as Q.

There are many ways to reduce the time spent in steps 4 and 6 of Algorithm U. However, steps 5 and 7 dominate the computation time.

18. Computing a coprime base for a finite set

The following algorithm uses binary splitting and Algorithm U to compute the natural coprime base for any finite set. Algorithm M. Given S, to print cb S:

1. If S = {}: Stop.

2. If #S = 1: Find a ∈ S. Print a if a ≠ 1. Stop.

3. Select T ⊆ S with #T = ⌊#S/2⌋.

4. Compute P ← cb T by Algorithm M recursively.

5. Compute Q ← cb(S − T) by Algorithm M recursively.

6. Print cb(P ∪ Q) by Algorithm U.

Theorem 18.1. Let S be a finite subset of a free coid. Then Algorithm M prints cb S.

Proof. By construction the output is a coprime base for T and for S − T, hence for S. Naturalness follows from Theorem 7.1.

Theorem 18.2. Let S be a finite susbet of a free coid. Define x = prod S. If m ≥ 1, 2^{m−1} ≥ 2 lg x, and 2^{k} ≥ #S ≥ 1 then Algorithm M finishes in M-time at most 4mk(8m^{3} + 28m^{2} + 19m + 4)(lg x)μ(6 lg x).

Proof. If #S = 1 then Algorithm M uses no M-time. Otherwise, by induction on k, step 4 uses M-time at most 4m(k−1)(8m^{3}+28m^{2}+19m+4)(lg prod T)μ(6 lg x), and step 5 uses M-time at most 4m(k−1)(8m^{3}+28m^{2}+19m+4)(lg prod(S−T))μ(6 lg x). Step 6 uses M-time at most 2m(8m^{3} +28m^{2} +19m+4)(2 lg x)μ(6 lg x) by Theorem 17.3. Add.

Part IV. Factorization

19. Computing ord

Let p and a be elements of a free coid, with p ≠ 1. I define reduce(p, a) = (i, a/p^{i}), where i is the largest integer such that p^{i} divides a. In particular i = ord_{p} a if p is a quasiprime for a. Algorithm E. Given (p, a), to print reduce(p, a):

1. If p does not divide a: Print (0, a) and stop.

2. Compute (j, b) ← reduce(p^{2}, a/p) by Algorithm E recursively.

3. If p divides b: Print (2j + 2, b/p) and stop.

4. Print (2j + 1, b).

Theorem 19.1. Let p and a be elements of a free coid, with p ≠ 1. Then Algorithm E prints reduce(p, a).

Proof. Induct on a.

If p does not divide a then reduce(p, a) = (0, a/p^{0}) = (0, a).

After step 2, by induction, a/p = (p^{2})^{j}b, with p^{2} not dividing b. If p divides b then a = p^{2j+2}(b/p), with p not dividing b/p, so reduce(p, a) = (2j + 2, b/p). Otherwise a = p^{2j+1}b, with p not dividing b, so reduce(p, a) = (2j + 1, b).

Theorem 19.2. Let p and a be elements of a free coid, with p ≠ 1. Define (i, c) = reduce(p, a). If 2^{k} > i + 1 then Algorithm E computes (i, c) in M-time at most (4k − 3)(1 + lg ap)μ(lg ap).

Proof. Induct on k. Note that k ≥ 1 since 2^{k} ≥ i + 2 ≥ 2.

Case 1: i is zero. Algorithm E uses M-time at most (1 + lg ap)μ(lg ap) in step 1; it then stops, since p does not divide a. Finally 4k − 3 ≥ 1.

Case 2: i is odd. Then j = (i−1)/2 in step 2 of Algorithm E so j+1 = (i+1)/2 < 2^{k−1}. By induction Algorithm E uses M-time at most (4k − 7)(1 + lg ap)μ(lg ap) for the recursive call. It also uses M-time at most (1 + lg ap)μ(lg ap) in step 1, (1 + lg p^{2})μ(lg p^{2}) + (1 + lg a)μ(lg a) for the computations of p^{2} and a/p in step 2, and (1 + lg bp)μ(lg bp) in step 3.

The total is at most μ(lg ap) times (4k − 7)(1 + lg ap) + 1 + lg ap + 1 + 2 lg p + 1 + lg a+1+lg bp = 4k−3+(4k−4) lg a+(4k−3−i) lg p = (4k−3)(1+lg ap)−lg a−i lg p.

Case 3: i is even and nonzero. As before the recursive call uses M-time at most (4k − 7)(1 + lg ap)μ(lg ap). The other computations use M-time at most (1 + lg ap)μ(lg ap) in step 1, (1 + lg p^{2})μ(lg p^{2}) + (1 + lg a)μ(lg a) in step 2, and (1 + lg bp)μ(lg bp) + (1 + lg b)μ(lg b) in step 3.

The total is at most μ(lg ap) times (4k − 7)(1 + lg ap) + 1 + lg ap + 1 + 2 lg p + 1 + lg a+1+lg bp+1+lg b = (4k−3)(1+lg ap)+1+(2−2i) lg p. Finally (2i−2) lg p > 1 since lg p ≥ 1.

Notes. Algorithm E is a simplified version of the algorithm I outlined in [4, section 22].

20. Factoring over a coprime base

Fix a. Let P be a coprime set not containing 1. Algorithm F below factors a into powers of elements of P, if possible; otherwise it proclaims failure.

Algorithm F prints the factorization of a as a list of pairs (p, n) meaning p^{n} where p ∈ P. In practice one could represent p in this pair by a pointer into P.

Algorithm F. Given (a, P), with P coprime and 1 ∉ P, to print the factorization of a into elements of P:

1. If P = {}: Proclaim failure if a ≠ 1. Stop.

2. If #P = 1: Find p ∈ P. Compute (n, c) ← reduce(p, a) by Algorithm E. If c ≠ 1, proclaim failure and stop. Otherwise print (p, n) and stop.

3. Select Q ⊆ P with #Q = ⌊#P/2⌋.

4. Compute y ← prod Q by Algorithm P.

5. Compute (b, c) ← (ppi, ppo)(a, y) by Algorithm PPIO.

6. Apply Algorithm F to (b, Q) recursively. If Algorithm F fails, proclaim failure and stop.

7. Apply Algorithm F to (c, P − Q) recursively. If Algorithm F fails, proclaim failure and stop.

Theorem 20.1. Let H be a free coid. Let P be a finite coprime subset of H not containing 1. Let a be an element of H. If P is a base for {a} then Algorithm F prints the factorization of a into elements of P. Otherwise Algorithm F proclaims failure.

Proof. Induct on #P.

Case 1: P = {}. Algorithm F correctly proclaims failure for a ≠ 1, and correctly prints nothing for a = 1.

Case 2: P = {p}. If Algorithm F does not proclaim failure, then it prints (p, n); and a/p^{n} = c = 1 so a = p^{n}. Conversely, if a = p^{n} for some n, then Algorithm E returns (n, 1), so Algorithm F does not proclaim failure.

Case 3: #P ≥ 2. Say P is a base for {a}. P is also a base for {y}, so P is a base for {b, c} by Theorem 7.5. If p ∉ Q then ord_{p} y = 0 so ord_{p} b = 0; thus Q is a base for {b}. Similarly P − Q is a base for {c}. By induction, Algorithm F prints the factorizations of b and c into elements of Q and P − Q respectively, which together form a factorization of a since bc = a; and Algorithm F does not proclaim failure.

Conversely, if Algorithm F does not proclaim failure, then P is a base for {b, c} by induction, hence for {a}.

Theorem 20.2. Let H be a free coid. Let P be a finite coprime subset of H not containing 1. Define x = prod P. Let a be an element of H. If 2^{m} ≥ #P ≥ 1 and 2^{k} > lg a + 1 then Algorithm F finishes in M-time at most

(4k − 3 + m(2k + 4)) lg a + (4k − 3 + \frac{m(m + 1)}{2}) lg x + (7k − 1 + \frac{m}{2}) #P − 3k − 2

times μ(lg ax).

Proof. Induct on m.

Case 1: #P = 1. Algorithm F uses M-time at most (4k − 3)(1 + lg ap)μ(lg ap) in step 2 by Theorem 19.2.

Case 2: #P ≥ 2. Then m ≥ 1, 2^{m−1} ≥ #Q ≥ 1, and 2^{m−1} ≥ #(P − Q) ≥ 1. Define y = prod Q and z = prod(P − Q). Also write T = 4k − 3 + (m − 1)(2k + 4) and U = 4k − 3 + (m − 1)m/2.

Algorithm F uses M-time at most (\frac{1}{2}#P − 1 + (m − 1) lg x)μ(lg x) in step 4 by Theorem 14.1 since #Q ≤ \frac{1}{2}#P and lg y ≤ lg x. In step 5 it uses M-time at most (3k +3+(2k +4) lg a+lg x)μ(lg ax) by Theorem 11.5. By induction it uses M-time at most (T lg b + U lg y + (7k − 1 + \frac{1}{2}(m − 1))#Q − 3k − 2)μ(lg by) in step 6 and (T lg c + U lg z + (7k − 1 + \frac{1}{2}(m − 1))#(P − Q) − 3k − 2)μ(lg cz) in step 7. The total is at most μ(lg ax) times

(\frac{1}{2}#P − 1 + (m − 1) lg x) + (3k + 3 + (2k + 4) lg a + lg x)
+ (T lg a + U lg x + (7k − 1 + \frac{1}{2}(m − 1)) #P − 6k − 4) ,

which equals the claimed bound.

21. Factoring a set over a coprime base

Let S be a set, and let P be a coprime set not containing 1. Algorithm G below factors each element a ∈ S into elements of P if P is a base for S; otherwise it proclaims failure.

Theorem 21.1. Let H be a free coid. Let P be a finite coprime subset of H not containing 1. Let S be a finite subset of H. Define x = prod P, y = prod S, and z = ppi(x, y). Define Q = {p ∈ P : ppi(z, p) = p}. Then P is a base for S if and only if Q is a base for S. Furthermore each element of Q divides y.

Thus Q contains only the elements of P that are relevant to S.

Proof. Q ⊆ P, so if Q is a base for S then P is a base for S.

Conversely, say P is a base for S. Take any p ∈ P dividing some element of S. Then ord_{p} x = 1 and ord_{p} y > 0, so ord_{p} z = 1, so ord_{p} ppi(z, p) = 1. For any q ∈ P other than p, ord_{q} p = 0 so ord_{q} ppi(z, p) = 0. Thus ppi(z, p) = p; i.e., p ∈ Q.

Finally, if p ∈ Q then ppi(z, p) = p so ord_{p} z = 1 so ord_{p} y > 0 so p divides y.

Algorithm G. Given (S, P), with P coprime and 1 ∉ P, to print the factorization of each element of S into elements of P:

1. If S = {}: Stop.

2. Compute x ← prod P by Algorithm P.

3. Compute y ← prod S by Algorithm P.

4. Compute z ← ppi(x, y) by Algorithm PPIO.

5. Compute D ← split(z, P) by Algorithm S.

6. Compute Q ← {p ∈ P : (p, p) ∈ D}.

7. If #S = 1: Apply Algorithm F to (y, Q), proclaiming failure if Algorithm F fails. Stop.

8. Select T ⊆ S with #T = ⌊#S/2⌋.

9. Apply Algorithm G to (T, Q) recursively.

10. Apply Algorithm G to (S − T, Q) recursively.

Theorem 21.2. Let S be a finite subset of a free coid. Let P be a finite coprime base for S, with 1 ∉ P. Then Algorithm G prints the factorization of each element of S into elements of P.

Proof. By Theorem 21.1, Q is a base for S. Induct on #S. If #S = 1 then S = {y} and step 7 prints the factorization of y. If #S ≥ 2 then Q is a base for T and for S − T; hence, by induction, Algorithm G prints the factorization of each element of T in step 9 and each element of S − T in step 10.

Theorem 21.3. Let S be a finite subset of a free coid. Let P be a finite coprime base for S, with 1 ∉ P. Define x = prod P and y = prod S. Algorithm G finishes in M-time at most μ(lg x^{2}y) times

\begin{matrix}3m + 3 + (6k + 6)(#S − 1) + (4.5m^{2} + 21.5m + 15) lg x \\ + ((9k^{2} + 44k + 32)n + 2.5k^{2} + 21k − 5) lg y \end{matrix}

if 2^{n} ≥ #S ≥ 1, 2^{k} > lg y + 1, 2^{m} ≥ lg x, and m ≥ 0.

Proof. Induct on n. Note that #S − 1 ≤ lg y. Similarly #P ≤ lg x since 1 ∉ P, and #Q ≤ lg prod Q ≤ lg y by Theorem 21.1. Write z = ppi(x, y).

Step 2 uses M-time at most (m + 1)(lg x)μ(lg x). This follows from Theorem 14.1 for #P ≥ 1. (For #P = 0, Algorithm P uses no M-time.) Similarly, step 3 uses M-time at most (k + 1)(lg y)μ(lg y).

Step 4 uses M-time at most (3m + 3 + (2m + 4) lg x + lg y)μ(lg xy) by Theorem 11.5.

Step 5 uses M-time less than (4.5m^{2} + 18.5m + 10)(lg x)μ(lg x^{2}). This follows from Theorem 15.4 for #P ≥ 1, since lg z ≤ lg x. (For #P = 0, Algorithm S uses no M-time.)

The total so far is at most μ(lg x^{2}y) times 3m + 3 + (4.5m^{2} + 21.5m + 15) lg x + (k + 2) lg y. This leaves

((6k + 6)(#S − 1) + ((9k^{2} + 44k + 32)n + 2.5k^{2} + 20k − 7) lg y) μ(lg x^{2}y)

unaccounted for in the claimed run time.

Case 1: #S = 1. Then step 7 uses M-time at most (2.5k^{2} + 20k − 7) lg y times μ(lg x^{2}y). This follows from Theorem 20.2 for #Q ≥ 1, since 2^{k} ≥ #Q. (For #Q = 0, Algorithm F uses no M-time; note that 2.5k^{2} + 20k − 7 > 0 since k ≥ 1.)

Case 2: #S ≥ 2. Then step 9 uses M-time at most μ(lg x^{2}y) times

3k + 3 + (6k + 6)(#T − 1) + (4.5k^{2} + 21.5k + 15) lg y
+ ((9k^{2} + 44k + 32)(n − 1) + 2.5k^{2} + 21k − 5) lg prod T

by induction since 2^{k} ≥ lg prod Q. Similarly, step 10 uses M-time at most μ(lg x^{2}y) times

3k + 3 + (6k + 6)(#(S − T) − 1) + (4.5k^{2} + 21.5k + 15) lg y
+ ((9k^{2} + 44k + 32)(n − 1) + 2.5k^{2} + 21k − 5) lg prod(S − T).

Add.

Notes. Algorithm G is faster than the algorithm of [2, Theorem 7].

In step 6 of Algorithm G one could proclaim failure if (p, c) ∈ D for some c ∉ {1, p}.

References

[1] —, International symposium on symbolic and algebraic computation ’90, Association for Computing Machinery, New York, 1990.

[2] Eric Bach, James Driscoll, Jeffrey Shallit, Factor refinement, Journal of Algorithms 15 (1993), 199–222.

[3] Eric Bach, Gary Miller, Jeffrey Shallit, Sums of divisors, perfect numbers, and factoring, SIAM Journal on Computing 15 (1986), 1143–1154.

[4] Daniel J. Bernstein, Detecting perfect powers in essentially linear time, to appear, Mathematics of Computation.

[5] Daniel J. Bernstein, Fast ideal arithmetic via lazy localization, in [10], 27–34.

[6] Jonathan M. Borwein, Peter B. Borwein, Pi and the AGM, Wiley, New York, 1987.

[7] Richard P. Brent, Fred G. Gustavson, David Y. Y. Yun, Fast solution of Topelitz systems of equations and computation of Padé approximants, Journal of Algorithms 1 (1980), 259–295.

[8] Jacques Calmet (editor), Algebraic algorithms and error-correcting codes 3, Lecture Notes in Computer Science 229, Springer-Verlag, Berlin, 1986.

[9] Bob F. Caviness (editor), Proceedings of EUROCAL ’85, volume 2, Lecture Notes in Computer Science 204, Springer-Verlag, Berlin, 1985.

[10] Henri Cohen (editor), Proceedings of the algorithmic number theory symposium 2, Lecture Notes in Computer Science 1122, Springer-Verlag, Berlin, 1996.

[11] George E. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition: preliminary report, SIGSAM Bulletin 8 (1974), 80–90.

[12] Jean Della Dora, Claire DiCrescenzo, Dominique Duval, About a new method for computing in algebraic number fields, in [9], 289–290.

[13] Joachim von zur Gathen, Representations and parallel computations for rational functions, SIAM Journal of Computing 15 (1986), 432–452.

[14] Guoqiang Ge, Recognizing units in number fields, Mathematics of Computation 63 (1994), 377–387.

[15] Erich Kaltofen, Sparse Hensel lifting, in [9], 4–17.

[16] Erich Kaltofen, Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, preprint.

[17] Donald E. Knuth, The art of computer programming, volume 2: seminumerical algorithms, 2nd edition, Addison-Wesley, Reading, Massachusetts, 1981.

[18] Heinz Lüneburg, On a little but useful algorithm, in [8], 296–301.

[19] Michael Pohst, Hans Zassenhaus, Algorithmic algebraic number theory, Cambridge University Press, Cambridge, 1989.

[20] Arnold Schönhage, Schnelle Berechnung von Kettenbruchentwicklugen, Acta Informatica 1 (1971), 139–144.

[21] Trevor J. Smedley, Detecting algebraic dependencies between unnested radicals: extended abstract, in [1], 292–293.

[22] Thomas Jan Stieltjes, Sur la théorie des nombres, Ann. Fac. Sci. Toulouse 4 (1890), 1–103.

[23] Jeremy T. Teitelbaum, On the computational complexity of the resolution of plane curve singularities, Mathematics of Computation 54 (1990), 797–837.

Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, IL 60607–7045

E-mail address: djb@pobox.com