problem of factoring integers, and then later adapted to the discrete log-

arithm problem. The ¬rst (heuristic) subexponential-time algorithm for

factoring integers, called the continued fraction method (not discussed

here), was introduced by Lehmer and Powers [56], and later re¬ned and

implemented by Morrison and Brillhart [66]. The ¬rst rigorously ana-

lyzed subexponential-time algorithm for factoring integers was introduced

by Dixon [34]. Algorithm SEF is a variation of Dixon™s algorithm, which

works the same way as Algorithm SEF, except that it generates relations

of the form (16.6) directly (and indeed, it is possible to prove a variant of

16.5 Notes 357

Theorem 16.1, and for that matter, Theorem 16.7, for random squares mod-

ulo n). Algorithm SEF is based on an idea suggested by Racko¬ (personal

communication).

Theorem 16.7 was proved by Can¬eld, Erd˝s, and Pomerance [23]. The

o

quadratic sieve was introduced by Pomerance [74]. Recall that the quadratic

sieve has a heuristic running time of

exp[(1 + o(1))(log n log log n)1/2 ].

This running time bound can also be achieved rigorously by a result of

Lenstra and Pomerance [58], and to date, this is the best rigorous running

time bound for factoring algorithms. We should stress, however, that most

practitioners in this ¬eld are not so much interested in rigorous running time

analyses as they are in actually factoring integers, and for such purposes,

heuristic running time estimates are quite acceptable. Indeed, the quadratic

sieve is much more practical than the algorithm in [58], which is mainly of

theoretical interest.

There are two other factoring algorithms not discussed here, but that

should anyway at least be mentioned. The ¬rst is the elliptic curve

method, introduced by Lenstra [57]. Unlike all of the other known

subexponential-time algorithms, the running time of this algorithm is sen-

sitive to the sizes of the factors of n; in particular, if p is the smallest prime

dividing n, the algorithm will ¬nd p (heuristically) in expected time

√

exp[( 2 + o(1))(log p log log p)1/2 ] · len(n)O(1) .

This algorithm is quite practical, and is the method of choice when it is

known (or suspected) that n has some small factors. It also has the ad-

vantage that it uses only polynomial space (unlike all of the other known

subexponential-time factoring algorithms).

The second is the number ¬eld sieve, the basic idea of which was intro-

duced by Pollard [73], and later generalized and re¬ned by Buhler, Lenstra,

and Pomerance [21], as well as by others. The number ¬eld sieve will split

n (heuristically) in expected time

exp[(c + o(1))(log n)1/3 (log log n)2/3 ],

where c is a constant (currently, the smallest value of c is 1.902, a result

due to Coppersmith [27]). The number ¬eld sieve is currently the asymp-

totically fastest known factoring algorithm (at least, heuristically), and it is

also practical, having been used to set the latest factoring record”the fac-

torization of a 576-bit integer that is the product of two primes of about the

358 Subexponential-time discrete logarithms and factoring

same size. See the web page www.rsasecurity.com/rsalabs/challenges/

factoring/rsa576.html for more details.

As for subexponential-time algorithms for discrete logarithms, Adleman

[1] adapted the ideas used for factoring to the discrete logarithm problem,

although it seems that some of the basic ideas were known much earlier.

Algorithm SEDL is a variation on this algorithm, and the basic technique

is usually referred to as the index calculus method. The basic idea of

the number ¬eld sieve was adapted to the discrete logarithm problem by

Gordon [40]; see also Adleman [2] and Schirokauer, Weber, and Denny [80].

For many more details and references for subexponential-time algorithms

for factoring and discrete logarithms, see Chapter 6 of Crandall and Pomer-

ance [30]. Also, see the web page www.crypto-world.com/FactorWorld.

html for links to research papers and implementation reports.

For more details regarding the security of signature schemes, as discussed

following Exercise 16.4, see the paper by Bellare and Rogaway [13].

Last, but not least, we should mention the fact that there are in fact

polynomial-time algorithms for factoring and discrete logarithms; however,

these algorithms require special hardware, namely, a quantum computer.

Shor [87, 88] showed that these problems could be solved in polynomial time

on such a device; however, at the present time, it is unclear when and if such

machines will ever be built. Much, indeed most, of modern-day cryptogra-

phy will crumble if this happens, or if e¬cient “classical” algorithms for

these problems are discovered (which is still a real possibility).

17

More rings

This chapter develops a number of other concepts concerning rings. These

concepts will play important roles later in the text, and we prefer to discuss

them now, so as to avoid too many interruptions of the ¬‚ow of subsequent

discussions.

17.1 Algebras

Let R be a ring. An R-algebra (or algebra over R) is a ring E, together

with a ring homomorphism „ : R ’ E. Usually, the map „ will be clear

from context, as in the following examples.

Example 17.1. If E is a ring that contains R as a subring, then E is an

R-algebra, where the associated map „ : R ’ E is just the inclusion map.

2

Example 17.2. Let E1 , . . . , En be R-algebras, with associated maps „i :

R ’ Ei , for i = 1, . . . , n. Then the direct product ring E := E1 — · · · — En

is naturally viewed as an R-algebra, via the map „ that sends a ∈ R to

(„1 (a), . . . , „n (a)) ∈ E. 2

Example 17.3. Let E be an R-algebra, with associated map „ : R ’ E,

and let I be an ideal of E. Consider the quotient ring E/I. If ρ is the

natural map from E onto E/I, then the homomorphism ρ —¦ „ makes E/I

into an R-algebra, called the quotient algebra of E modulo I. 2

Example 17.4. As a special case of the previous example, consider the ring

R[X], viewed as an R-algebra via inclusion, and the ideal of R generated by

f , where f is a monic polynomial. Then R[X]/(f ) is naturally viewed as an

R-algebra, via the map „ that sends c ∈ R to [c]f ∈ R[X]/(f ). If deg(f ) > 0,

359

360 More rings

then „ is an embedding of R in R[X]/(f ); if deg(f ) = 0, then R[X]/(f ) is the

trivial ring, and „ maps everything to zero. 2

In some sense, an R-algebra is a generalization of the notion of an exten-

sion ring. When the map „ : R ’ E is a canonical embedding, the language

of R-algebras can be used if one wants to avoid the sloppiness involved in

“identifying” elements of R with their image under „ in E, as we have done

on occasion.

In this text, we will be particularly interested in the situation where E is

an algebra over a ¬eld F . In this case, E either contains a copy of F , or

is itself the trivial ring. To see this, let „ : F ’ E be the associated map.

Then since the kernel of „ is an ideal of F , it must either be {0F } or F . In

the former case, „ is injective, and so E contains an isomorphic copy of F .

In the latter case, our requirement that „ (1F ) = 1E implies that 1E = 0E ,

and so E is trivial.

Subalgebras

Let E be an R-algebra with associated map „ : R ’ E. A subset S of E is

a subalgebra if S is a subring containing img(„ ). As an important special

case, if „ is just the inclusion map, then a subring S of E is a subalgebra if

and only if S contains R.

R-algebra homomorphisms

There is, of course, a natural notion of a homomorphism for R-algebras.

Indeed, it is this notion that is our main motivation for introducing R-

algebras in this text. If E and E are R-algebras, with associated maps

„ : R ’ E and „ : R ’ E , then a map ρ : E ’ E is called an R-algebra

homomorphism if ρ is a ring homomorphism, and if for all a ∈ R, we have

ρ(„ (a)) = „ (a).

As usual, if ρ is bijective, then it is called an R-algebra isomorphism,

and if R = R , it is called an R-algebra automorphism.

As an important special case, if „ and „ are just inclusion maps, then a

ring homomorphism ρ : E ’ E is an R-algebra homomorphism if and only

if the restriction of ρ to R is the identity map.