e . Hint: mimic the “lifting”

that v is uniquely determined modulo p

ˆ

procedure discussed in §13.3.2.

(c) Using parts (a) and (b), design and analyze an e¬cient algorithm

that takes the matrix A and the prime p as input, together with a

bound H on the absolute value of the numerator and denominator of

the entries of the vector v that is the unique (rational) solution to

the equation v A = w. Your algorithm should run in time polynomial

in the length of H, the length of p, and the sum of the lengths of the

entries of A and w. Hint: use rational reconstruction, but be sure to

fully justify its application.

Note that in the previous exercise, one can use the theory of determinants

to derive good bounds, in terms of the lengths of the entries of A and w, on

the size of the least prime p such that A is invertible modulo p (assuming

A is invertible over the rationals), and the length of the numerator and

denominator of the entries of rational solution v to the equation v A = w.

The interested reader who is familiar with the basic theory of determinants

is encouraged to establish such bounds.

The next two exercises illustrate how Gaussian elimination can be

adapted, in certain cases, to work in rings that are not necessarily ¬elds.

Let R be an arbitrary ring. A matrix B ∈ Rm—n is said to be in row eche-

lon form if there exists a pivot sequence (p1 , . . . , pr ), with 0 ¤ r ¤ m and

1 ¤ p1 < p2 < · · · < pr ¤ n, such that the following holds:

• for i = 1, . . . , r, all of the entries in row i of B to the left of entry

(i, pi ) are zero;

• for i = 1, . . . , r, we have B(i, pi ) = 0;

• all entries in rows r + 1, . . . , m of B are zero.

334 Matrices

Exercise 15.14. Let R be the ring Zpe , where p is prime and e > 1. Let

π := [p] ∈ R. The goal of this exercise is to develop an e¬cient algorithm

for the following problem: given a matrix A ∈ Rm—n , with m > n, ¬nd a

vector v ∈ R1—m such that vA = 01—n but v ∈ πR1—m .

(a) Show how to modify the extended Gaussian elimination algorithm

to solve the following problem: given a matrix A ∈ Rm—n , compute

M ∈ Rm—m and B ∈ Rm—n , such that M A = B, M is invertible,

and B is in row echelon form. Your algorithm should run in time

O(mn(m + n)e2 len(p)2 ). Assume that the input includes the values

p and e. Hint: when choosing a pivot element, select one divisible

by a minimal power of π; as in ordinary Gaussian elimination, your

algorithm should only use elementary row operations to transform

the input matrix.

(b) Using the fact that the matrix M computed in part (a) is invertible,

argue that none of its rows belong to πR1—m .

(c) Argue that if m > n and the matrix B computed in part (a) has

pivot sequence (p1 , . . . , pr ), then m ’ r > 0 and if v is any one of the

last m ’ r rows of M , then vA = 01—n .

(d) Give an example that shows that the ¬rst r rows of B need not be

linearly independent and that the last m’r rows of M need not span

the kernel of the R-linear map that sends w ∈ R1—m to wA ∈ R1—n .

Exercise 15.15. Let R be the ring Z , where > 1 is an integer. You are

given a matrix A ∈ Rm—n . Show how to e¬ciently compute M ∈ Rm—m

and B ∈ Rm—n such that M A = B, M is invertible, and B is in row echelon

form. Your algorithm should run in time O(mn(m + n) len( )2 ). Hint: to

zero-out entries, you should use “rotations””for integers a, b, d, s, t with

d = gcd(a, b) = 0 and as + bt = d,

and for row indices r, i, a rotation simultaneously updates rows r and i of a

matrix C as follows:

b a

(C(r), C(i)) ← (sC(r) + tC(i), ’ C(r) + C(i));

d d

observe that if C(r, j) = [a] and C(i, j) = [b] before applying the rotation,

then C(r, j) = [d] and C(i, j) = [0] after the rotation.

15.6 Notes

While a trivial application of the de¬ning formulas yields a simple algorithm

for multiplying two m—m matrices over a ring R that uses O(m3 ) operations

15.6 Notes 335

in R, this algorithm is not the best, asymptotically speaking. The currently

fastest algorithm for this problem, due to Coppersmith and Winograd [28],

uses O(mω ) operations in R, where ω < 2.376. We note, however, that the

good old O(m3 ) algorithm is still the only one used in almost any practical

setting.

16

Subexponential-time discrete logarithms and

factoring

This chapter presents subexponential-time algorithms for computing dis-

crete logarithms and for factoring. These algorithms are based on a common

technique, which makes essential use of the notion of a smooth number.

16.1 Smooth numbers

If y is a non-negative real number, and m is a positive integer, then we say

that m is y-smooth if all prime divisors of m are at most y.

For 0 ¤ y ¤ x, let us de¬ne Ψ(y, x) to be the number of y-smooth integers

up to x. The following theorem gives us a lower bound on Ψ(y, x), which will

be crucial in the analysis of our discrete logarithm and factoring algorithms.

Theorem 16.1. Let y be a function of x such that

y log x

’ ∞ and u := ’∞

log x log y

as x ’ ∞. Then

Ψ(y, x) ≥ x · exp[(’1 + o(1))u log log x].

Proof. Let us write u = u + δ, where 0 ¤ δ < 1. Let us split the primes up

to y into two sets: the set V “very small” primes that are at most y δ /2, and

the other primes W that are greater than y δ /2 but at most y. To simplify

matters, let us also include the integer 1 in the set V .

By Bertrand™s postulate (Theorem 5.7), there exists a constant C > 0

such that |W | ≥ Cy/ log y for su¬ciently large y. By the assumption that

y/ log x ’ ∞ as x ’ ∞, it follows that |W | ≥ 2 u for su¬ciently large x.

To derive the lower bound, we shall count those integers that can be built

up by multiplying together u distinct elements of W , together with one

336

16.2 An algorithm for discrete logarithms 337

element of V . These products are clearly distinct, y-smooth numbers, and

each is bounded by x, since each is at most y u y δ = y u = x.

If S denotes the set of all of these products, then for x su¬ciently large,

we have

|W |

|S| = · |V |

u

|W |(|W | ’ 1) · · · (|W | ’ u + 1)

· |V |

=

u!

u

|W |

≥ · |V |

2u

u

Cy

≥ · |V |

2u log y

u’δ

Cy

· |V |.

=

2 log x

Taking logarithms, we have

log |S| ≥ (u ’ δ)(log y ’ log log x + log(C/2)) + log |V |

= log x ’ u log log x + (log |V | ’ δ log y) +

O(u + log log x). (16.1)

To prove the theorem, it su¬ces to show that

log |S| ≥ log x ’ (1 + o(1))u log log x.

Under our assumption that u ’ ∞, the term O(u + log log x) in (16.1) is

o(u log log x), and so it will su¬ce to show that the term log |V | ’ δ log y