Previous Page Home Next Page

be surprised if anyone regularly factors numbers of

Algorithms, G. L. Mullen and P. Shiue, eds., Amer. Math. The problem

size lo” without special form during the present cen-

sot., 1994. of factoring

tury.” He was also shown to be too cautious in a few

I121 C. Pomerance, The number field sieve, pp. 465-480 in integers has

years. The choice of a 129D integer for the RSA

Mathematics of Computation 1943-1993: A HalfCentury fascinated

challenge number in 1977 151 was apparently moti-

of ComputationalMathemutics, W. Gautschi, ed., Amer. mathematicians

vated by an estimate of Ron Rivest that to factor such

Math. Sot., 1994. for a long time

an integer would require more than “40 quadrillion

[I31 C. Pometance, J. W. Smith, and R. Tuler, A pipeline ar-

years” on a computer much faster than any that exist

chitecture for factoring large integers with the quadratic

even today. However, this challenge integer was fac-

sieve algorithm, SIAMJ. Comput. 17(1988), 387-403.

tored in 1994.

[14] R. L. Rivest, Dr. Ron Rivest on the difficulty of factoring,

first published inCipher?ext: L%eRSA Newsktte˜ vol. 1,

no. 1, fall 1993, and reprinted, in an updated form, in an

appendix on pp. 361-364 in S. Garfinkel, PGR Pretty

In 1964, there was practically no organized activity

Goodpriuacy, O™Reilly & Associates, 1995.

in factoring integers, and so this entry is based on the

f151 M. J. Wiener, Efficient DES key search, TR-244, May

remarks in 121.

1994, School of Computer Science, Carleton University,

Ottawa, Canada. Presented at the Rump Session of

The largest generally hard integer that had been fac-

Crypto ˜93. Available through anonymous ftp from

tored by 1974 was F,, the 7-th Fermat number,

ripem.msu.edu:/pub/crvpt/docs/des-key-˜.˜.

21B + 1, which is 39D. (Today it would not be classi-

fied as “generally hard,” since the special number field

Appendices sieve handles numbers of this type much more effi-

ciently than general ones. Also, as another techni-

cal point, the integer that was factored was 257 * F,,

AppendkA:Hidoricales-

since the use of a multiplier speeded up the algo-

ofthed3Ekultyoff

rithm.) F, had been factored in 1970 by Mike

The problem of factoring integers has fascinated Morrison and John Brillhart, but their paper describ-

mathematicians for a long time, and there is a fa- ing this work was only published in the 1975 D. H.

mous quote of Gauss on what a fundamental ques- Lehmer special issue of&&. Comp. In those days,

tion this is. A concrete estimate of how hard it might integer factorization was not fashionable, and there

be was provided in 1874 by W. Stanley Jevons, the was not much interest in going after records. There-

English economist and logician. He conjectured 171 fore inspection of the published literature is not ad-

that nobody but he would ever know the factors of equate to assess the state of the art. Experts who were

the 10D integer 8616460799. However, he was active in this area in the 1970s say that they thought

proved wrong by Bancroft Brown around 1925, and that numbers of 45D were doable with the algorithms

perhaps by others even earlier. In an unpublished and machines available then, and so 45D is the fig-

manuscript, a copy of which was kindly provided ure used here.

by John Brillhan, Brown explained how he obtained

the factorization 1984: This is the Sandia factorization of Jim Davis,

Diane Holdridge, and Gus Simmons.

8616460799 = 96079 * 89681.

1994: This is RSA129, the RSA challenge integer of

In 1967, John Brillhart and John Selfridge [21 stated 1977, which was factored by a world-wide collabora-

that ˜I... in general nothing but frustration can be tive effort organized and led by Derek Atkins,

expected to come from an attack on a number of 25 Michael Graff, Arjen Lenstra, and Paul Leyland [l].

or more digits, even with the speeds available in mod-

ern computers.” By 1970 their estimate was out of If we also consider integers of a special form, then the

date because of a new factoring method that allowed i62D integer (12i5i - 1) / 11 provides another record.

Mike Morrison and John Brillhart to factor an inte- It was factored in 1994 by Henk Boender, Joe Buhler,

ger of 39D. In 1976, Richard Guy t61 stated “I shall Scott Huddleston, Marije Huizing, Walter Lioen,

la

THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - SUMMER 1995 CRYPTOBYTES

Page 51

Previous Page Home Next Page

mate equates 1 megaflop with 1 mips, which is not

Peter Montgomery, Herman te Riele, Robby Robson,

very accurate, and is based on the June 1995 version

Russell Ruby, and Dik Winter.

of the TOP500 report 141.) IBM mainframes shipped

in 1994 (which was a record year in terms of main-

Appendixc:Gxnput@powerof

frame computing power, although not in dollar vol-

histodd-ns

ume of sales) amounted to only 2 * lo5 mips.

According to John Brillhart, integer factorizations in

It seems

the early 1970s usually used up only about an hour of Appendix E: Moore™s “Iaw”

imprudent

cpu time on the mainframes of those days, which are

to assume

There is some skepticism whether this law will con-

typically rated at l-10 mips.

Moore™s “Law”

tinue to hold much longer. Line widths will eventu-

will be violated

ally be so small that entire new technologies might

The 1984 Sandia factorization used 9.5 cpu hours on

any time soon.

be needed, architectural improvements (speculative

a Cray X-MP, which is on the order of 100 mips.

execution, etc.) might run into the exponential com-

plexity blowup, and so on. Even if the bare tech-

1994: This is the Atkins et al. estimate tll for the

nologies are not a barrier, economics might present

computation, which used the ppmpqs algorithm.

one, since the costs of state of the art fabrication fa-

Since then a 119D integer has been factored by Scott

cilities are also escalating. However, such concerns

Contini, Bruce Dodson, Arjen Lenstra, and Peter

are not new, and were already present a decade ago,

Montgomery in about 250 MY using gnfs (the gen-

and yet progress has continued unhindered. Thus it

eral number field sieve), suggesting that today the

seems imprudent to assume Moore™s “Law” will be

RSA129 factorization could be carried out in about

violated any time soon. Since state of the art micro-

1000 MY instead of the 5000 MY that was used. See

processors are already running close to 500 mips, the

131 for details.

projection that by 2004 the typical processor will

have a rating of 1000 mips (compared to around 10

AppendixD:Qmentcomputingpower

mips today) seems safe. Beyond that, there are big-

ger question marks. Even if raw processor speed con-

The oft-quoted figure of 30M users of the Internet is

tinues to increase, memories might be more of a

questionable, as it is obtained by assuming there are

bottleneck. Since most fast factorization algorithms

10 users per computer. However, the estimate that

rely on substantial memories to perform sieving op-

about 3M machines of one kind or another are

erations, they are often already limited by memory

hooked up to the Internet seems much more solid.

system performance more than by the processor.

Since many of them are old, an average 10 mips rat-

However, this is a problem that is afflicting an in-

ing seems reasonable for them.

creasing range of problems. Therefore there are

strong incentives towards dealing with it, and again

There are well over 108 PCs in the world. Since sev-

it seems imprudent to assume it will form an insur-

eral tens of millions of them already have the 486

mountable barrier.

chips, which are usually rated at tens of mips, the es-

The TV set-top

timate of 3 * lOa mips is conservative. On the other

boxes being

hand, most of these machines are not easily usable AppedixF:Numberofcomputem

designed today

for factoring, since they are not networked, do not

have more

Since there will be about lOi people on Earth in

have enough memory, do not have operating systems

computing

2014, a projection of 10” computers implies that

that allow for background jobs to run easily in idle

power than

there will be over 10 computers per person. This may

time, etc. All these factors will change in a few years,

the Cray- I,

seem fanciful, but we should remember that there are

but now it would be hard to harness a large fraction

the first

many embedded microprocessors in everyday appli-

of all the PCs in a factoring project.

supercomputer.

ances such as cars, dishwashers, etc., and they will be

getting increasingly powerful. To provide voice rec-

We might note that all the supercomputers in the

ognition capability for the coffee pot will require con-

world (about 103 in total) have a computing power

siderable processing power. (The TV set-top boxes

of about 3 . lo6 mips, with several sites having be-

being designed today have more computing power

tween 5% and 10% of of that capacity. (This esti-

RSA LABORATORIES

1 9 9 5 -THE TECHNICAL NEWSLETTER OF

CRYPTOBYTES SUMMER

Eiil

Page 52

Previous Page Home Next Page

The continued fraction method, which was the

than the Cray-1, the first supercomputer. The new

32-bit video game machines, of which tens of mil- most widely used method in the 197Os, appears

lions are expected to be sold each year, will have (at least for the most common variant) to have nm-

similar power.) We might note, as a forerunner of ning time

what will be common, that there were two fax ma-

chines among the approximately 1600 processors in Lh, l/2, c3 + o(l)1 as 72 0 ,

the RSA129 project.

where c, = 2l/* = 1.4142 . . .

There is still a question, even if we assume that there

will be many computers around, of whether they will AppendixH:Comparisonofnmningt.imes

all be networked together, and whether their com- ofalgprithnrs

puting power will be easily accessible. Will there be

computing-power brokers, selling time on millions of The o(1) terms in the estimates of running times of

machines? Will people be willing to tolerate some- factorization algorithms are usually not computed

body else running jobs on their machines, even in explicitly. Instead, to estimate how long an algorithm

spare time? with asymptotic running time Lln, z.r, a + o(l)1

should take to factor an integer n, one takes the

observed running timeX on an integer m and com-

AppendhGRmmingtimeofalgorithms

putesX * Lln, ˜1, al /L[m, V, al. This has worked well

In a variant of the standard notation, we define in practice. This method does ignore various impor-

tant practical aspects, such as the need for memory

and communication capacity as well as cpu cycles,

Lln, v, al = exp<u - (log fz)” - (log log tzP) >,

but those have been overcome in the past either

where log n refers to the natural logarithm of n. through better algorithms or general technological

improvements, so it seems reasonable to continue to

The heuristic running time (there are no rigorous ignore them.

proofs, but experience and heuristics support the cal-

culations) of the gnfs to factor an integer n is

Lln, l/3, co + o(l)1 as n 0 , Public key cryptosystems such as RSA and DSA There are some

require use of large moduli because known general problems in

where cg = (64/W/3 = 1.9229 . . . . There is also a algorithms for factoring integers and computing dis- which the best

variant, due to Don Coppersmith, which does not crete logarithms are subexponential, and so hardware algorithms

seem to be practical, that allows the replacement of improvements by themselves lead to substantial known are

q, by cl = 1.3018. . . . See 18,121 for presentations of progress. In addition, there have been steady and exponential,

the gnfs. rapid improvements in algorithms, On the other and where

hand, there are some problems in which the best al- there has been

The special number field sieve, which factors effi- gorithms known are exponential, and where there has no recent

ciently integers of the form& 1 6, for example, where been no recent algorithmic improvement. We cite algorithmic

a and 6 are small, and k large (k can also be small, but here as an example attacks on DSA, the US Digital improvement

then has to fall into certain ranges) has running time Signature Algorithm, that do not use the structure of

the multiplicative group of integers modulo the large

Lb, l/3, c2 + o(l)1 as n 0 , basic primep. The DSA uses discrete exponentia-

tion modulo a primep, but the exponents are com-

where ca = (32/9)˜/3 = 1.5262 . . . . puted modulo a prime q such that q dividesp - 1.

CIlis is the Schnorr method that speeds up the algo-

Previous methods, such as variants of the quadratic rithm.) Therefore all the integers are inside an abe-

sieve algorithm, have running times of the form lian group of order q. To break DSA, one can either

solve the general discrete log problem modulo p,

which can be done using a variant of the number field

L[n, l/2, 1 + o(l)] as n 0

liiii

THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - SUMMER CRYPTOBYTES

199S

Page 53

Previous Page Home Next Page

cost) and would find a single DES key in about 4

sieve, or else work inside the group of order q. The

hours. What this shows is that special purpose hard-

best algorithms for the second attack are those of Dan

Shanks and John Pollard, both of which take about ware can be of great help in breaking DES. On the

& operations. Since these 6 operations involve other hand, general integer factorization and dis-

multiplications modulop, though, even for q of 160 crete logarithm algorithms do not benefit that much

bits andp of 1024 bits or more, it would take at least from special designs, and it is the threat of the free