Factorization of the tenth Fermat number

MATHEMATICS OF COMPUTATION

Volume68,Number225,January1999,Pages429–451

S0025-5718(99)00992-8

F ACTORIZATION OF THE TENTH FERMAT NUMBER

RICHARD P.BRENT

Abstract.We describe the complete factorization of the tenth Fermat num-

ber F10by the elliptic curve method(ECM).F10is a product of four prime

factors with8,10,40and252decimal digits.The40-digit factor was found

after about140M?op-years of computation.We also discuss the complete fac-

torization of other Fermat numbers by ECM,and summarize the factorizations

of F5,...,F11.

1.Introduction and historical summary

For a nonnegative integer n,the n-th Fermat number is F n=22n+1.It is known that F n is prime for0≤n≤4,and composite for5≤n≤23.Also,for n≥2,the factors of F n are of the form k2n+2+1.In1732Euler found that641=5·27+1 is a factor of F5,thus disproving Fermat’s belief that all F n are prime.No Fermat primes larger than F4are known,and a probabilistic argument makes it plausible that only a?nite number of F n(perhaps only F0,...,F4)are prime.

The complete factorization of the Fermat numbers F6,F7,...has been a chal-lenge since Euler’s time.Because the F n grow rapidly in size,a method which factors F n may be inadequate for F n+1.Historical details and references can be found in[21,35,36,44,74],and some recent results are given in[17,26,27,34].

In the following,p n denotes a prime number with n decimal digits(not necessarily the same at each occurrence).Similarly,c n denotes a composite number with n decimal digits.

Landry[41]factored F6=274177·p14in1880,but signi?cant further progress was only possible with the development of the digital computer and more e?cient algorithms.In1970,Morrison and Brillhart[55]factored

F7=59649589127497217·p22

by the continued fraction method.Then,in1980,Brent and Pollard[18]factored

F8=1238926361552897·p62

by a modi?cation of Pollard’s“rho”method[6,58].The larger factor p62of F8was ?rst proved prime by Williams[18,§4]using the method of Williams and Judd[75].

If it had been invented earlier,the rho method could have been used to factor F7(with a little more di?culty than F8,see[18,Table2]).Similarly,the multiple-polynomial quadratic sieve(MPQS)method[59,70],which is currently the best Received by the editor February2,1996and,in revised form,May20,1997.

1991Mathematics Subject Classi?cation.Primary11Y05,11B83,11Y55;Secondary11–04, 11A51,11Y11,11Y16,14H52,65Y10,68Q25.

Key words and https://www.wendangku.net/doc/7b14130250.html,putational number theory,Cunningham project,ECM,elliptic curve method,factorization,Fermat number,F9,F10,F11,integer factorization.

c 1999American Mathematical Society

429

430R.P.BRENT

“general-purpose”method for composite numbers of up to about100decimal digits, could have been used to factor both F7and F8,but it was not available in1980.

Logically,the next challenge after the factorization of F8was the factorization of F9.It was known that F9=2424833·c148.The148-digit composite number resisted attack by methods such as Pollard rho,Pollard p±1,and the elliptic curve method(ECM),which would have found“small”factors.It was too large to factor by the continued fraction method or its successor,MPQS.The di?culty was?nally overcome by the invention of the(special)number?eld sieve(SNFS),based on a new idea of Pollard[43,61].In1990,Lenstra,Lenstra,Manasse and Pollard,with the assistance of many collaborators and approximately700workstations scattered around the world,completely factored F9by SNFS[44,45].The factorization is F9=2424833·7455602825647884208337395736200454918783366342657·p99.

In§8we show that it would have been possible(though more expensive)to complete the factorization of F9by ECM.

F10was the“most wanted”number in various lists of composite numbers pub-lished after the factorization of F9(see,for example,the list in Update2.9of[21]). F10was proved composite in1952by Robinson[64],using P′e pin’s test on the SWAC.A small factor,45592577,was found by Selfridge[65]in1953(also on the SWAC).Another small factor,6487031809,was found by Brillhart[20]in1962on an IBM704.Brillhart later found that the cofactor was a291-digit composite. Thus,it was known that F10=45592577·6487031809·c291.

This paper describes the complete factorization of https://www.wendangku.net/doc/7b14130250.html,ing ECM we found a 40-digit factor p40=4659775785220018543264560743076778192897on October20, 1995.The252-digit cofactor c291/p40=13043···24577was proved to be prime us-ing the method of Atkin and Morain[1].Later,a more elementary proof was found, using Selfridge’s“Cube Root Theorem”(see§9).Thus,the complete factorization is

F10=45592577·6487031809·4659775785220018543264560743076778192897·p252.

So far,this summary has been chronological,but now we backtrack,because F11 was completely factored in1988,before the factorization of F9and F10.In fact,

F11=319489·974849·167988556341760475137·3560841906445833920513·p564, where p564=17346···34177.The two6-digit factors were found by Cunning-ham[21,29]in1899,and remaining factors were found by the present author in May1988.

The reason why F11could be completely factored before F9and F10is that the di?culty of completely factoring numbers by ECM is determined mainly by the size of the second-largest prime factor of the number.The second-largest prime factor of F11has22digits and is much easier to?nd by ECM than the40-digit factor of F10.

A brief summary of the history of factorization of F5,...,F11is given in Table1. For a similar history of F12,...,F22,see[25,p.148].

In§§2–4we describe some variants of ECM and their performance,and in§5we describe some implementations of ECM which were used in attempts to factor F10 and other composite numbers.Details of the factorization of F10are given in§6. As details of the factorization of F11have not been published,apart from two brief

FACTORIZATION OF FERMAT NUMBERS BY ECM431 https://www.wendangku.net/doc/7b14130250.html,plete factorization of F n,n=5,...,11

n Factorization Method Date Comments

5p3·p7Trial division1732Euler

6p6·p14See[74]1880Landry

7p17·p22CFRAC1970Morrison and Brillhart

8p16·p62B-P rho1980Brent and Pollard(p16,p62)

See[18,75]1980Williams(primality of p62)

9p7·p49·p99Trial division1903Western(p7)

SNFS1990Lenstra et al(p49,p99)

10p8·p10·p40·p252Trial division1953Selfridge(p8)

Trial division1962Brillhart(p10)

ECM1995Brent(p40,p252)

11p6·p 6·p21·p22·p564Trial division1899Cunningham(p6,p 6)

ECM1988Brent(p21,p22,p564)

ECPP1988Morain(primality of p564)

announcements[9,11],we describe the computation in§7.Further examples of factorizations obtained by ECM are given in§8.

Rigorously proving primality of a number as large as the564-digit factor of F11 is a nontrivial task.In§9we discuss primality proofs and“certi?cates”of primality for the factors of F n,n≤11.

Attempts to factor Fermat numbers by ECM are continuing.For example,27-digit factors of F13and F16have recently been found[13,17].The smallest Fermat number which is not yet completely factored is F12.It is known that F12has at least seven prime factors,and

F12=114689·26017793·63766529·190274191361·1256132134125569·c1187. The prospects for further progress in factoring F12are discussed in§10.

The reader who is interested in numerical results but not in details of the imple-mentation and performance prediction of ECM can safely skip forward to§6.

1.1.Acknowledgements.Thanks are due to Hendrik Lenstra,Jr.,for the ECM algorithm which made the factorization of F10and F11possible;and to Peter Mont-gomery and Hiromi Suyama for their practical improvements to ECM.John Pollard provided some of the key ideas with his“p?1”and“rho”methods.John Brillhart, Richard Crandall,Wilfrid Keller,Donald Knuth,John Selfridge and Daniel Shanks provided historical information,references,and/or corrections to drafts of this pa-per.Bruce Dodson,Arjen Lenstra,Peter Montgomery,Robert Silverman and Sam Wagsta?,Jr.provided information about other attempts to factor F10.Fran?c ois Morain proved the primality of the564-digit factor of F11.An anonymous referee provided valuable comments which helped to improve the exposition.John Can-non provided access to the Magma package.Bob Gingold graciously volunteered spare computer cycles on a SparcCenter2000.The ANU Supercomputer Facility provided computer time on Fujitsu VP100,VP2200/10,and VPP300vector pro-cessors.The ANU-Fujitsu CAP Project provided access to a Fujitsu AP1000,and the ACSys Cooperative Research Centre provided access to eight DEC alphas.

432R.P.BRENT

2.Variants of ECM

The elliptic curve method(ECM)was discovered by H.W.Lenstra,Jr.[46]in 1985.Practical re?nements were suggested by various authors[8,23,50,51,72]. We refer to[45,52,62,71]for a general description of ECM,and to[24,69]for relevant background.

Suppose we attempt to?nd a factor of a composite number N,which we can assume not to be a perfect power[2],[44,§2.5].Let p be the smallest prime factor of N.In practice it is desirable to remove small factors(up to say104)by trial division before applying ECM,but we only need assume p>3.

We describe the algorithms in terms of operations in the?nite?eld K=GF(p)= Z/p Z.In practice,when p is unknown,we usually work modulo N and occasionally perform GCD computations which will detect any nontrivial factor of N(probably p,though possibly a di?erent factor of N).Because there is a natural ring ho-momorphism from Z/N Z to Z/p Z,working modulo N can be regarded as using a redundant representation for elements of Z/p Z.

Pollard’s p?1method[57]uses the multiplicative group of the?nite?eld K. ECM is analogous,but uses a group G de?ned on an elliptic curve.Although this makes group operations more expensive,a crucial advantage of ECM is that several di?erent groups can be tried in an attempt to?nd a factor.

There is no loss of generality in assuming that the elliptic curve is given in Weierstrass normal form

y2=x3+ax+b,

(1)

where a and b are constants such that

(2)

4a3+27b2=0

in K.G consists of the set of points(x,y)∈K×K which lie on the curve,and a “point at in?nity”O.A commutative and associative group operation is de?ned in a standard way[69].In accordance with the usual convention we write the group operation additively.The zero element of G is O.

Let g=|G|be the order of G.We have g=p+1?t,where t satis?es Hasse’s inequality t2<4p.The number of curves with given t can be expressed in terms of the Kronecker class number of t2?4p(see[46]).

In practice,to avoid computation of square roots,we select a pseudo-random parameter a and initial point(x1,y1)on the curve,and then compute b from(1). If desired,the condition(2)can be checked by a GCD computation.

2.1.Other models.We use the words“model”and“form”interchangeably.The Weierstrass form(1)is not the most e?cient for computations involving group operations.With(1)we have to perform divisions modulo N.These are expensive because they involve an extended GCD computation.To avoid divisions modulo N, we can replace(x,y)by(x/z,y/z)in(1)to get a homogeneous Weierstrass equation

y2z=x3+axz2+bz3.

(3)

The points(x,y,z)satisfying(3)are thought of as representatives of elements of P2(K),the projective plane over K,i.e.the points(x,y,z)and(cx,cy,cz)are regarded as equivalent if c=0mod p.We write(x:y:z)for the equivalence class containing(x,y,z).The additive zero element O is(0:1:0)and we can test for it by computing GCD(N,z).

FACTORIZATION OF FERMAT NUMBERS BY ECM433 Montgomery[50]suggested using the form

by2=x3+ax2+x

(4)

or,replacing(x,y)by(x/z,y/z)as above,

by2z=x3+ax2z+xz2.

(5)

Corresponding to the condition(2)we now have the condition b(a2?4)=0.

Not every elliptic curve can be expressed in the form(4)or(5)by rational transformations.However,by varying a in(4)or(5),we get a su?ciently large class of pseudo-random curves.The exact value of b in(4)or(5)is not important, but it is signi?cant whether b is a quadratic residue(mod p)or not.In general we get two di?erent groups,of order p+1±t,by varying b.

Assume that we start with a point P1=(x1:y1:z1)on(5).For positive integer n,we write P n=nP1and suppose P n=(x n:y n:z n).Montgomery[50,§10] shows in a direct way that,for positive integer m,n such that P m=±P n,we have an addition formula

x m+n z m+n =

z|m?n|(x m x n?z m z n)2 x|m?n|(x m z n?z m x n)2

(6)

and a duplication formula

x2n z2n =

(x2n?z2n)2

4x n z n(x2n+ax n z n+z2n)

.

(7)

An alternative derivation of(6)–(7),using addition and duplication formulas for the Jacobian elliptic function sn2(u),is given in[23,p.422].This derivation makes

the reason for associativity clear.

Note that(6)–(7)do not specify the y-coordinate.Fortunately,it turns out that the y-coordinate is not required for ECM,and we can save work by not computing

it.In this case we write P n=(x n::z n).Since(x:y:z)+(x:?y:z)=O, ignoring y amounts to identifying P and?P.

Montgomery[50,§10]shows how(6)and(7)can be implemented to perform an

addition and a duplication with11multiplications(mod N).

2.2.The?rst phase.The?rst phase of ECM computes P r for a large integer r.

Usually r is the product of all prime powers less than some bound B1.There is no need to compute r explicitly.By the prime number theorem,log r～B1as B1→∞. (Here and below,“log”without a subscript denotes the natural logarithm.)

From(6)–(7),we can compute the x-and z-components of(P1,P2n,P2n+1)or (P1,P2n+1,P2n+2)from the x-and z-components of(P1,P n,P n+1).Thus,from the binary representation of the prime factors of r,we can compute(x r::z r)in O(log r)=O(B1)operations,where each operation is an addition or multiplication mod N.In fact,(x r::z r)can be computed with about K1B1multiplications mod N and a comparable number of additions mod N,where K1=11/log2.If z1=1,then K1can be reduced to10/log2.For details,see Montgomery[50,§10].

At the end of the?rst phase of ECM we check if P r=O by computing

GCD(z r,N)(note the comment above on ring homomorphisms).If the GCD is nontrivial then the?rst phase of ECM has been successful in?nding a factor of N. Otherwise we may continue with a second phase(see§3)before trying again with a di?erent pseudo-random group G.

434R.P.BRENT

2.3.The starting point.An advantage of using(4)or(5)over(1)or(3)is that the group order is always a multiple of four(Suyama[72];see[50,p.262]).Also,it is possible to ensure that the group order is divisible by8,12or16.For example, ifσ/∈{0,±1,5},

u/v=(σ2?5)/(4σ),

x1/z1=u3/v3,

(8)

a+2=(v?u)3(3u+v)/(4u3v),

then the curve(5)has group order divisible by12.As a starting point we can take (x1::z1).

3.The second phase

Montgomery and others[8,50,51,54]have described several ways to improve Lenstra’s original ECM algorithm by the addition of a second phase,analogous to phase2of the Pollard p?1method.We outline some variations which we have implemented.Phase1is the same in all cases,as described in§2.2.

We assume that the form(5)is used with starting point P1=(x1::z1)given by(8).Bounds B2≥B1>0are chosen in advance.For example,if our aim is to?nd factors of up to about35decimal digits,we might choose B1=106and B2=100B1(see§4.4).In the following we assume that B2 B1,so B2?B1 B2. We de?ne B3=π(B2)?π(B1) B2/log B2.The time required for phase2is approximately proportional to B3.

Suppose the group order g has prime factors g1≥g2≥···.Phase1will usually be successful if g1≤B1.We say“usually”because it is possible that a prime factor of g occurs with higher multiplicity in g than in r,but this is unlikely and can be neglected when considering the average behaviour of ECM.Phase2is designed to be successful if g2≤B1

In§§3.1–3.4we describe several di?erent versions of phase2(also called“con-tinuations”because they continue after phase1).Some versions are di?cult to implement using only the formulae(6)–(7).For this reason,some programs use Montgomery’s form(5)for phase1and convert back to Weierstrass form(1)or(3) for phase2.For details of the transformation see[4,§4.2].

3.1.The standard continuation.Suppose phase1has computed Q=P r such that Q=O.The“standard continuation”computes sQ=(x rs::z rs)for each prime s,B1

compute

GCD

s

z rs mod N,N

where the product mod N is taken over a su?ciently large set of s,and backtrack if the GCD is composite.This reduces the average cost of a GCD essentially to that of a multiplication mod N.

There is no advantage in using phase2if sQ is computed using the standard binary method,which takes O(log s)group operations.It is much more e?cient to precompute a small table of points2dQ,where0

FACTORIZATION OF FERMAT NUMBERS BY ECM 435

for some odd s 1,we can compute min(s 1+2D,s 2)Q ,where s 2is the next prime,using only one group operation.Thus,we can compute sQ for a sequence of values of s including all primes in (B 1,B 2]and possibly including some composites (if 2D is smaller than the maximal gap between successive primes in the interval),with one group operation per point.Provided D is at least of order log B 2,the work for phase 2is reduced from O (B 2)group operations to O (B 3)group operations.

The standard continuation can be implemented e?ciently in O (log N log B 2)bits of storage.It is not necessary to store a table of primes up to B 2as the odd primes can be generated by sieving in blocks as required.Even storing the primes to √B 2is unnecessary,because we can sieve using odd integers 3,5,7,9,....The sieving does not need to be very e?cient,because most of the time is spent on multiple-precision arithmetic to perform group operations.Sieving could be replaced by a fast pseudo-prime test,because it does not hurt ECM if a few composites are included in the numbers generated and treated as primes.

3.2.The improved standard continuation.The standard continuation can be improved—Montgomery’s form (5)can be used throughout,and most group op-erations can be replaced by a small number of multiplications mod N .The key idea [50,§4]is that we can test if GCD(z rs ,N )is nontrivial without comput-ing sQ .We precompute 2dQ for 0

There is an analogy with Shanks’s baby and giant steps [66,p.419]:giant steps involve a group operation (about 11multiplications)and possibly an extended GCD computation,but baby steps avoid the group operation and involve only K 2≤3multiplications.

To decide on the table size D ,note that setting up the table and computation

of the points mQ requires about D +B 2/(2D )applications of (6).If storage is not a consideration,the optimal D is approximately 2However,provided √B 2>D log B 2,the setting up cost is o (B 3),and the overall cost of phase 2

is about K 2B 3multiplications mod N .Thus,storage requirements for an e?cient implementation of the improved standard continuation are not much greater than for the standard continuation.

3.3.The birthday paradox continuation.The “birthday paradox”continua-tion is an alternative to the (improved)standard continuation.It was suggested

436R.P.BRENT

in [8]and has been implemented in several of our programs (see §5)and in the programs of A.Lenstra et al.[4,31,45].

There are several variations on the birthday paradox idea.We describe a ver-sion which is easy to implement and whose e?ciency is comparable to that of the improved standard continuation.Following a suggestion of Suyama,we choose a positive integer parameter e .The choice of e is considered below.For the moment the reader can suppose that e =1.

Suppose,as in §3.1,that Q is the output of phase 1.Select a table size T .If storage permits,T should be about √B 3;otherwise choose T as large as storage constraints allow (for reasonable e?ciency we only need T e log B 3).Generate T pseudo-random multiples of Q ,say Q j =q e j Q for j =1,...,T .There is some advantage in choosing the q j to be linear in j ,i.e.,q j =k 0+k 1j for some pseudo-random k 0,k 1(not too small).In this case the Q j can be computed by a “?nite di?erence”scheme with O (eT )group operations because the e -th di?erences of the multipliers q e j are constant.Another possibility is to choose q j to be a product of small primes.For example,in our programs C–D (see §5)we use a set of 2 log 2T odd primes and take q j to be a product of log 2T odd primes from this set,the choice depending on the bits in the binary representation of j ?1.This scheme requires O (eT log log T )group operations and can be vectorized.

After generating the T points Q j ,we generate B 3/T further pseudo-random

points,say Q k =q e k Q ,where the q k are distinct from the q j .The choice q k =2

k is satisfactory.For each such point Q k ,we check if Q k =±Q j for j =1,...,T .This can be done with K 2T multiplications mod N ,as in the description of the improved standard continuation in §3.2.If T is su?ciently large,it is worthwhile to make the z -coordinates of Q j and Q k unity by extended GCD computations,which reduces K 2to 1.(To reduce the number of extended GCDs,we can generate the points Q k in batches and reduce their z -coordinates to a common value before performing one extended GCD.)Note that the points Q k do not need to be stored as only one (or one batch)is needed at a time.We only need store O (T )points.

It is easy to see that most of the computation for the birthday paradox version of phase 2amounts to the evaluation (mod N )of a polynomial of degree T at B 3/T points.Thus,certain fast polynomial evaluation schemes can be used [8,38,56].

Both the improved standard continuation and the birthday paradox continuation make approximately B 3comparisons of points which are multiples of Q ,say nQ and n Q ,and usually succeed if g 2≤B 1and n ±n is a nontrivial multiple of g 1.The improved standard continuation ensures that |n ?n |is prime,but the birthday paradox continuation merely takes pseudo-random n and n .Since g 1is prime,it would appear that the improved standard continuation is more e?cient.However,taking the parameter e >1may compensate for this.The number of solutions of

x 2e =1mod g 1

(9)is GCD(2e,g 1?1).Thus,by choosing e as a product of small primes,we increase the expected number of solutions of (9).In fact,if 2e =2e 13e 25e 3···,it can be shown that the expected value of GCD(2e,q ?1)for a random large prime q is (e 1+1)(e 2+1)(e 3+1)···.Since g 1is the largest prime factor of the group order g ,it is reasonable to assume similar behaviour for GCD(2e,g 1?1).The number of solutions of equation (9)is relevant because we expect phase 2to succeed if g 2≤B 1and (q j /q k )2e =1mod g 1.

FACTORIZATION OF FERMAT NUMBERS BY ECM437 The parameter e should not be chosen too large,because the cost of generating the points Q j and Q k is proportional to e.To ensure that this cost is negligible, we need e T.In practice,a reasonable strategy is to choose the largest e from the set{1,2,3,6,12,24,30}subject to the constraint32e

3.4.The FFT continuation.Pollard suggested the use of the FFT to speed up phase2for his p?1method,and Montgomery[51]has successfully implemented the analogous phase2for ECM.The FFT continuation may be regarded as an e?cient generalisation of both the improved standard continuation and the birthday paradox continuation.We have not implemented it because of its complexity and large storage requirements.

https://www.wendangku.net/doc/7b14130250.html,parison of continuations.It is natural to ask which of the above ver-sions of phase2is best.We initially implemented the birthday paradox continu-ation because of its simplicity.Also,the asymptotic analysis in[8,§7]indicated that it would be faster than the(improved)standard continuation.However,this was on the assumption that an asymptotically fast polynomial evaluation scheme would be used.In practice,the polynomial degrees are unlikely to be large enough for such a scheme to be signi?cantly faster than standard polynomial evaluation. In our most recent implementation of ECM[13,Program G]we have used the improved standard continuation because of its slightly lower storage requirements and better(predicted)performance for factors of up to40decimal digits.If storage requirements and program complexity are not major considerations,then the FFT continuation is probably the best.

4.Performance of ECM

In order to predict the performance of ECM,we need some results on the distri-bution of prime factors of random integers.These results and references to earlier work may be found in[39,73].

4.1.Prime factors of random integers.Let n1(N)≥n2(N)≥...be the prime factors of a positive integer N.The n j(N)are not necessarily distinct.For convenience we take n j(N)=1if N has less than j prime factors.

For k≥1,suppose that1≥α1≥...≥αk≥0.Following Vershik[73],we de?neΦk=Φk(α1,...,αk)by

Φk=lim

M→∞#{N:1≤N≤M,n j(N)≤Nαj for j=1,...,k}

M

.

Informally,Φk(α1,...,αk)is the probability that a large random integer N has its j-th largest prime factor at most Nαj,for j=1,...,k.The cases k=1and k=2are relevant to ECM(see§§4.2–4.4).It is convenient to de?neΦ1(α1)=1if α1>1,andΦ1(α1)=0ifα1<0.Vershik[73,Theorem1]shows that

Φk= α

k

α

k?1

θk

···

α

1

θ2

Φ1

θk

1?θ1?···?θk

dθ1...dθk?1dθk

θ1...θk?1θk

.

(10)

Knuth and Trabb Pardo[39]observe an interesting connection with the distri-bution of cycle lengths in a random permutation[33,67].In fact,the distribution of the number of digits of the j-th largest prime factors of n-digit random integers is asymptotically the same as the distribution of lengths of the j-th longest cycles in random permutations of n objects.

438R.P.BRENT

We de?ne

ρ(α)=Φ1(1/α)forα>0,

ρ2(α)=Φ2(1,1/α)forα≥1,

(11)

μ(α,β)=Φ2(β/α,1/α)for1≤β≤α.

Informally,ρ(α)is the probability that nα1≤N,ρ2(α)is the probability that nα2≤N,andμ(α,β)is the probability that both nα2≤N and nα1≤Nβ,for a large random integer N with largest prime factor n1and second-largest prime factor n2. Note thatρ(α)=μ(α,1)andρ2(α)=μ(α,α).

The functionρis usually called Dickman’s function after Dickman[30],though some authors refer toΦ1as Dickman’s function,and Vershik[73]calls?1=Φ 1the Dickman-Goncharov function.

It is known(see[8])thatρsatis?es a di?erential-di?erence equation

αρ (α)+ρ(α?1)=0

(12)

forα≥1.Thus,ρ(α)may be computed by numerical integration from

ρ(α)=1

α

α

α?1

ρ(t)dt

(13)

forα>1.The functionμmay be computed from[8,eqn.(3.3)]

μ(α,β)=ρ(α)+

α?1

α?β

ρ(t)

α?t

dt

(14)

for1≤β≤α.The formula forμgiven in[71,p.447]is incorrect,as can be seen by considering the limit asβ→1+.

The results(12)–(14)follow from Vershik’s general result(10),although it is possible to derive them more directly,as in[8,38,39].

Sharp asymptotic results forρare given by de Bruijn[22,48],and an asymptotic result forμis stated in[8].To predict the performance of phase1of ECM it is enough to know that

ρ(α?1)ρ(α)～?logρ(α)～αlogα

(15)

asα→∞.

4.2.Heuristic analysis of phase1.We?rst give a simple,heuristic explanation of why phase1of ECM works.Assume that,so far as its largest prime factor g1is concerned,the group order g behaves like a random integer near p.This is not quite correct,but is an accurate enough approximation to obtain asymptotic results.In§4.4we take known divisors of g into account.

Letα=log p/log B1,so B1=p1/α.The probability that one curve succeeds in ?nding the factor p is close to the probability that g1≤B1,and can be approxi-mated byρ(α).Thus,the expected number of curves for success is C1=1/ρ(α).As each curve requires about K1B1=K1p1/αmultiplications(mod N),the expected number of multiplications(mod N)is

W(α)=K1p1/α/ρ(α).

(16)

Di?erentiating with respect toα,we see that the minimum W(α)occurs when log p=?α2ρ (α)/ρ(α).Using(12)and(15),we obtain asymptotic results for the

FACTORIZATION OF FERMAT NUMBERS BY ECM 439

optimal parameters:

log p =αρ(α?1)ρ(α)～α2log α,(17)

log B 1=ρ(α?1)ρ(α)～αlog α,(18)

log C 1=?log ρ(α)～αlog α,(19)

log W =log K 1?d dα(αlog ρ(α))～2αlog α,(20)

log(B 1/C 1)=

?α2d dα log ρ(α)α ～α.(21)The result (21)is more delicate than the other asymptotic results because it involves cancellation of the terms of order αlog αin (18)and (19).

From (17)and (20)we obtain log W ～ 2log p log log p (22)

as p →∞.Thus,W =O (p )for any >0.

4.3.Lenstra’s analysis of phase 1.Modulo an unproved but plausible assump-tion regarding the distribution of prime factors of random integers in “short”inter-vals,Lenstra [46]has made the argument leading to (22)rigorous.He shows that phase 1of ECM,when applied to a composite integer N with smallest prime factor p ,will ?nd p in an expected number W 1(p )=exp

,(23)of multiplications (mod N ),where the “o (1)”term tends to zero as p →∞.The expected running time is

T 1(p,N )=M (N )W 1(p ),

where M (N )is the time required to multiply numbers modulo N .

The factor M (N )is important because we are interested in Fermat numbers N =F n =22n +1which may be very large.In practice,ECM is only feasible on F n for moderate n :the limit is about the same as the limit of feasibility of P′e pin’s test (currently n ≤22,see [27]).

4.4.Heuristic analysis of phase 2.Lenstra’s result (23)applies only to phase 1and assumes that the Weierstrass form is used.To predict the improvement derived from phase 2and the use of Montgomery’s form,we have to use heuristic arguments.We assume that the group order g behaves (so far as the distribution of its largest two prime factors are concerned)like a random integer near p/d ,where d takes account of known small divisors of g .If Montgomery’s form is used with the curve chosen as in §2.3,then d =12.

If ECM is used with parameters B 1and B 2,and the (improved)standard con-tinuation is applied,then we expect a factor to be found if g 2≤B 1and g 1≤B 2.If α=log(p/d )/log B 1and β=log B 2/log B 1,then (by our heuristic assumption)the probability that this occurs for any one curve is μ(α,β).Thus,the expected number of curves required by ECM is C (α,β)=1/μ(α,β),and (assuming that μis small)the probability of success after at most t curves is

1?(1?μ(α,β))t 1?exp(?t/C ).

(24)

440R.P.BRENT

If the birthday paradox continuation is used,the performance depends on the exponent e,and it is possible for phase2to succeed with g1>B2.From(10),the probability of success for one curve is approximately

1φ(2e) 1/α

1?ψ

ψ

1?exp

?γB3(d/p)θ

Φ1

ψ

1?θ?ψ

dθdψ

θψ

,

where the sum is over theφ(2e)possible values of g1mod2e,γranges over the corresponding values of GCD(2e,g1?1),andα=log(p/d)/log B1>2.Assuming close to the optimal choice of parameters for factors of30to40decimal digits, numerical integration indicates that the expected cost of the birthday paradox continuation(without fast polynomial evaluation)is15%to20%more than for the(improved)standard continuation if e=6,and9%to14%more if e=12. Because the analysis is simpler,in the following we assume the improved standard continuation.

To choose optimal parameters,we note that the time to perform both phases on one curve is proportional to K1B1+K2B3,provided overheads such as table initialization are negligible.The constants K1and K2depend on details of the implementation(see§3).

If we knew p in advance,we could choose B1and B2to minimize the expected run time,which is proportional to the expected number of multiplications mod N:

W=(K1B1+K2B3)/μ(α,β).

Recall thatαandβare functions of B1and B2,so this is a simple problem of minimization in two variables.Suppose that the minimum is W opt.Tables of optimal parameters are given in[4,8,45,51,71],with each paper making slightly di?erent assumptions.In Table2we give a small table of log10W opt for factors of D decimal digits.We assume that K1=11/log2,K2=1,and log10p D?0.5. Some computed values ofτ(p)are also shown in Table2,where

τ(p)=

(log W opt)2 log p log log p

,

so

W opt=exp

τ(p)log p log log p

.

McKee[49]gives plausible reasons why the practical performance of ECM may be slightly better than predicted in Table2.A limited amount of experimental data[8,45,51]supports McKee’s analysis.Thus,the table should be taken only as a rough(and slightly conservative)guide.

Since the expected run time is insensitive to changes in B1and B2near the optimal values,it is not important to choose them accurately.This is fortunate, as in practice we do not usually know p in advance.Various strategies have been suggested to overcome this di?culty.Our strategy has been to increase B1as a function of the number of curves t which have been tried,using the fact that for the optimal choice we expect B1/t to be about330for30-digit factors and to be fairly insensitive to the size of the factor.Given B1,we choose B2so the time for phase2 is about half that for phase1(this choice is not far from optimal).If B1 106this gives B2 100B1.

Once a factor p has been found,we can compute the e?ciency E,de?ned as the ratio of the expected time to?nd p with optimal parameters to the expected time

FACTORIZATION OF FERMAT NUMBERS BY ECM441

Table2.Expected work for ECM

digits D log10W optτ

207.35 1.677

309.57 1.695

4011.49 1.707

5013.22 1.716

6014.80 1.723

with the parameters actually used.For an example in which we started with B1 too small but gradually increased it to a value close to optimal,see Table3.

From the asymptotic behaviour of the functionsρ(α)andμ(α,β),it can be shown that the expected speedup S because of the use of phase2(standard continuation), compared to just using phase1,is of order log log p.It is argued in[8,§7]that the birthday paradox continuation gives a speedup of order log p(though only if asymptotically fast polynomial evaluation is used;for our implementations the speedup is of order log log p).The speedup for the FFT continuation is probably of order log p at most.Although these speedups are important in practice,they are theoretically insigni?cant,because they can be absorbed into the o(1)term in Lenstra’s result(23).Thus,we expectτ(p)→2as p→∞,independent of whether phase2is used.Table2shows that the convergence is very slow and thatτ(p) 1.7 for p in the25to45digit range.

We note a consequence of(24)which may be of cryptographic interest[63].If t is much larger than C,say t=100C,then the probability of failure is exp(?100),so we are almost certain to?nd a factor.On the other hand,if t is much smaller than C,say t=C/100,then1?exp(?t/C) t/C 0.01is small,but not exponentially so.Thus,ECM has a non-negligible chance of?nding factors which are much larger than expected.For example,if the work performed is su?cient to?nd30-digit factors with probability0.5,then with the same work there is about one chance in 100of?nding a factor of40digits and about one chance in10,000of?nding a factor of50digits(we do not attempt to be precise because the probabilities depend to some extent on how the parameters B1and B2are chosen).

5.Some ECM implementations

For future reference,we describe several implementations of ECM.Further details are given in[13,§5].

A.Our?rst implementation was written in1985,mainly in Pascal,but with some assembler to speed up large-integer multiplications.It used Montgomery’s forms(4)and(5)for phase1,and converted back to Weierstrass normal form(1)for phase2,which used the birthday paradox idea.Rational preconditioning[56]was used to speed up polynomial evaluation in phase2.The implementation achieved K1=10/log2and K2=1/2(recall that,as in§2.2–§3.3,the number of multi-plications mod N per curve is about K1B1+K2B3).Program A ran on various machines,including Sun3and VAX,and found many factors of up to25decimal digits[19].

B.A simple Turbo Pascal implementation was written in1986for an IBM PC[10].The implementation of multiple-precision arithmetic is simple but in-e?cient.Program B is mainly used to generate tables[19],taking into account

442R.P.BRENT

algebraic and Aurifeuillian factors[12],and accessing a database of over230,000 known factors.As a byproduct,program B can produce lists of composites which are used as input to other programs.

C.When a vector processor1became available early in1988,a Fortran program MVFAC was written(based on program A,with some improvements and simpli?-cations).Vectorization is accomplished by working on a number of elliptic curves in parallel during phase1.Phase2implements the birthday paradox idea as in§3.3. During phase2the program works on only one curve at a time,but takes advantage of the vector units during polynomial evaluation.Unlike program A,both phases use Montgomery’s form(5),with K1=11/log2and K2=1.The initial point is usually chosen to ensure that the group order is divisible by12,as described in§2.3. Multiple-precision arithmetic(with base226)in the inner loops is performed using double-precision?oating-point operations(?ops).INT and DFLOAT operations are used to split a product into high and low-order parts.Operations which are not time-critical,such as input and output,are performed using the MP package[5]. Program C found the factorization of F11(see§7)and many factors,of size up to 40decimal digits,needed for[16,19].Keller[37]used program C to?nd factors up to39digits of Cullen numbers.

D.A modi?cation of MVFAC also runs on other machines with Fortran compil-ers,e.g.,Sun4workstations.For machines using IEEE?oating-point arithmetic, the base must be reduced to224.Although the workstations do not have vector units,the vectorized code runs e?ciently because of the e?ect of amortizing loop startup overheads over several curves and keeping most memory accesses in a small working set(and hence in the cache).Program D found the p40factor of F10 (see§6).

5.1.The multiplication algorithm.Most of the cost of ECM is in performing multiplications mod N.Our programs all use the classical O(w2)algorithm to multiply w-bit numbers.Karatsuba’s algorithm[38,§4.3.3]or other“fast”algo-rithms[26,28]would be preferable for large w.The crossover point depends on details of the implementation.Morain[54,Ch.5]states that Karatsuba’s method is worthwhile for w≥800on a32-bit workstation.The crossover point on a64-bit vector processor is probably slightly larger.

Programs B–D do not take advantage of the special form of Fermat numbers when doing arithmetic mod N.However,the mod operation is implemented e?-ciently.For programs C and D the operation X←Y×Z mod N is coded as a single routine.As Y is multiplied by each digit d i of Z(starting with the most signi?cant digit)and the sum accumulated in X,we also predict a quotient digit q i,multiply N by q i,and subtract.The predicted quotient digit can di?er from the correct value by one,because a slightly redundant representation of the intermedi-ate results allows a small error to be corrected at the next step(when working in base B,digits in the range[0,B]are permitted).Also,the result of the operation is only guaranteed to lie in the interval[0,2N)and to be correct mod N.With these re?nements,the operation X←Y×Z mod N can be performed almost as fast as X←Y×Z.For w-bit numbers,program C performs9(w/26)2+O(w)?ops per multiplication mod N;this takes4(w/26)2+O(w)clock cycles on the VP2200/10.

1Initially a Fujitsu VP100with7.5nsec clock cycle;this machine was upgraded in mid-1991 to a Fujitsu VP2200/10with4.0nsec(later3.2nsec)clock cycle and theoretical peak speed of 1,000M?op(later1,250M?op).Times quoted for the VP2200are for the faster version.

FACTORIZATION OF FERMAT NUMBERS BY ECM443 If the number N to be factored is a composite divisor of2n±1,then the el-liptic curve operations can be performed mod2n±1rather than mod N.At the end of each phase we can compute a GCD with N.Because we can perform the reductions mod2n±1using binary shift and add/subtract operations,which are much faster(for large n)than multiply or divide operations,a signi?cant speedup may be possible.This idea was not implemented in programs B–D,but was used successfully in programs which found factors of F13and F16,see[13,17].

6.F actorization of F10

When ECM was implemented on the Fujitsu VP100in March1988,some of the ?rst numbers which we attempted to factor were the Fermat numbers F9,F10,F11 and F12,using variants of program C.We were soon successful with F11(see§7), but not with the other Fermat numbers,apart from rediscovering known factors. We continued attempts to factor F10by ECM.The phase1limit B1was gradually increased.However,there were some constraints on B1.Batch jobs were limited to at most two hours and,to make e?cient use of the vector units,we had to complete several curves in that time.The time for t curves done simultaneously was proportional to t+t1/2,where t1/2depended on the startup cost of vector operations.

We ran about2,000curves with B1=60,000on the VP100in the period March 1988to late1990.Each run on the VP100took slightly less than two hours for63 curves,with t1/2 10.The VP100was upgraded to a VP2200in1991,and we ran about17,360curves with B1=200,000on the VP2200in the period August1991 to August1995.Each run on the VP2200took slightly less than two hours for62 curves,with t1/2 14.The improvement in speed over the VP100was partly due to rewriting the inner loop of program C to reduce memory references and improve the use of vector registers.

In September1994we started running program D on one or two60Mhz Super-Sparc https://www.wendangku.net/doc/7b14130250.html,ually we used one processor for F10and one for F12.In July 1995six more60Mhz SuperSparc processors became available for a limited period. We attempted to factor F10on all eight SuperSparcs using spare computer time. Details are given in Table3.

In Table3,F is an estimate of the expected number of times that the factor p40should be found with the given B1and number of curves(see§4.4).E is an estimate of the e?ciency compared to the optimal choice of B1 3,400,000.The programs used the birthday paradox continuation,but the estimates of E and F assume the improved standard continuation with B2=100B1,so they are only approximate(see§4.4).The last row of the table gives totals(for number of curves and F)and weighted means(for B1and E).

The p40factor of F10was found by a run which started on October14and ?nished on October20,1995.The run tried10curves with B1=2,000,000in about114hours of CPU time,148hours elapsed wall-clock time.

From the factorizations of p40±1given in§9,it is easy to prove that p40is prime,and also to see why the Pollard p±1methods did not?nd p40.

The252-digit cofactor c291/p40was rigorously proved to be prime by two inde-pendent methods(see§9).

6.1.In retrospect.From column F of Table3,it appears that we were fortunate to?nd p40as soon as we did.The probability is about1?exp(?0.2434) 0.22.

444R.P.BRENT

Table3.ECM runs on F10

B1curves F E machine(s)and dates

6×1042,0000.00100.14VP100,Mar1988–Nov1990

2×10517,3600.09100.42VP2200,Aug1991–Aug1995

5×1057000.01520.69Sparc×2,Sep1994–Jul1995

1064800.02620.87Sparc×8,Jul1995–Aug1995

2×1069000.11000.98Sparc×8,Aug1995–Oct1995

2.9×10521,4400.24340.63

We know of some other attempts.Bruce Dodson tried about100curves with B1=2×106,Peter Montgomery tried about1,000curves with B1≤107(mean value unknown),Robert Silverman tried about500curves with B1=106,and Samuel Wagsta?tried“a few dozen”curves with150,000≤B1≤400,000.There were probably other attempts of which we are unaware,but the size of the known composite factor of F10(291decimal digits)reduced the number of attempts.For example,Montgomery’s Cray program was restricted to inputs of at most255digits, and Wagsta?did not use the Maspar[31]because it would have required a special “size33”program.

From column E of the table,it is clear that the runs on the VP100and VP2200 were ine?cient.We should have implemented a form of checkpointing so that B1 could be increased to at least106,allowing us to take more than two hours per set of curves.At the time we did not know that the unknown factor had40decimal digits,though by mid-1995we were reasonably con?dent that it had at least35 digits.Our general strategy was to increase B1gradually,guided by estimates of the optimal B1and the expected number of curves for factors of30–40digits.

6.2.The computational work.Each curve on a60Mhz SuperSparc takes about 5.7×10?6B1hours of CPU time.If a60Mhz SuperSparc is counted as a60-Mips machine,then our computation took about240Mips-years.This is comparable to the340Mips-years estimated for sieving to factor F9by SNFS[44].(SNFS has since been improved,so the340Mips-years could now be reduced by an order of magnitude,see[32,§10].)

Since the inner loops of programs C and D use?oating-point arithmetic,M?ops are a more appropriate measure than Mips.The VP2200/10is rated at1250M?op (peak performance).If our factorization of F10had been performed entirely on the VP2200,it would have taken about6weeks of machine time,or140M?op-years. This is only75minutes on a1Tera?op machine.

The number of multiplications(mod N)is a machine-independent measure of the work to factor N.Each curve takes about22.9B1such multiplications.Overall, our factorization of F10took1.4×1011multiplications(mod N),where N=c291. (Table2predicts3.3×1011with the optimal choice of parameters.)Numbers mod c291were represented with38digits and base226(on the VP100/VP2200)or with 41digits and base224(on the Sparc),so each multiplication(mod N)required more than104?oating-point operations.

6.3.The group order.The successful elliptic curve and starting point are de?ned by(5)and(8),withσ=14152267(derived from the starting date and time October

FACTORIZATION OF FERMAT NUMBERS BY ECM445 14,15:22:54).Explicitly,we can take the elliptic curve in the form(4)as by2=x3+1597447308290318352284957343172858403618x2+x mod p40. This may also be written as by2=x(x?k)(x?1/k)mod p40,where

k=1036822225513707746153523173517778785047.

b is any quadrati

c non-residue(mo

d p40),e.g.b=5.Th

e group order is

g=p40+1?3674872259129499038

=22·32·5·149·163·197·7187·18311·123677·226133·314263·4677853. The probability that a random integer near g/12has largest prime factor at most 4677853and second-largest prime factor at most314263is about5.8×10?6.The phase1limit for the successful run was B1=2×106,but program D?nds p40with B1as small as314263if the same curve and starting point are used.

7.F actorization of F11

After the factorization of F8in1980,no one predicted that F11would be the next Fermat number to be completely factored.Program C,described in§5,was implemented on a Fujitsu VP100in March1988.After failing to?nd any new factors of F9and F10,we compiled“large”versions of program C,suitable for F11 and F12,and checked them by?nding the known prime factors of these numbers.

A large version of program C took slightly less than one hour for20curves with B1=16,000on the number c606=F11/(319489·974849).On May13,1988,a 22-decimal digit factor

p22=3560841906445833920513=213·7·677·p14+1

was found by phase2.We had previously tried68curves unsuccessfully with B1 15,000.Overall it took about2.8×107multiplications(mod c606)and slightly less than four hours of machine time to?nd p22.Dividing c606by p22gave a584-digit composite number c584.

The next run of program C,on May17,1988,found a21-digit factor p21=167988556341760475137=214·3·373·67003·136752547+1

of c584,again using20curves with B1=16,000.It was surprising that a larger factor(p22)had been found?rst,but because of the probabilistic nature of ECM there is no guarantee that smaller factors will be found before larger ones.Overall, it took about3.6×107multiplications(mod c606or c584)and less than?ve hours of machine time to?nd both factors by ECM.It would have been feasible to?nd p21(but not p22)by the Pollard p?1method.

The quotient had564digits and it passed a probabilistic primality test[38,Algo-rithm P].If this test is applied to a composite number,the chance that it incorrectly claims the number is prime is less than1/4.We ran many independent trials,so we were con?dent that the quotient was indeed prime and that the factorization of F11was complete.This was veri?ed by Morain,as described in§9.The complete factorization of F11was announced in[9]:

F11=319489·974849·167988556341760475137·3560841906445833920513·p564.

446R.P.BRENT

8.Additional examples

To show the capabilities of ECM,we give three further examples.Details and other examples are available in[14].These examples do not necessarily illustrate typical behaviour of ECM.

In December1995,using program C with B1=370,000,D=255,e=6,we found the40-digit factor

p 40=9409853205696664168149671432955079744397

of p252?1,where p252is the largest prime factor of F10.See§9for the application to proving primality of p252.The curve is de?ned as in§2.3withσ=48998398, and the group order is

g=22·3·5·17·312·53·67·233·739·5563·7901·20201·57163·309335137. The largest prime factor g1of g is about836B1,which illustrates the power of the birthday paradox continuation.Note that GCD(2e,g1?1)=12.

In November1995,Montgomery[53]found the47-digit factor

p47=12025702000065183805751513732616276516181800961

of5256+1,using B1=3,000,000with his FFT continuation.The group order is g=26·3·5·7·23·997·43237·554573·659723·2220479·2459497·903335969.

In April1997,using a slight modi?cation of program D on a250Mhz DEC alpha,we“rediscovered”the factor

p49=7455602825647884208337395736200454918783366342657

of F9.Of course,this factor was already known(see§1),but it is interesting to see that it could have been found by ECM.We used the equivalent of about73,000 curves with B1=107;the number of curves predicted as in§4.4is about90,000. (The predicted optimal value of B1is about3×107,but for operational reasons we used a smaller value.)

The“lucky”curve is de?ned as in§2.3withσ=862263446.The group order is 22·32·52·7·331·1231·1289·6277·68147·1296877·9304783·9859051·44275577.

9.Primality proofs

In[7]we gave primality certi?cates for the prime factors of F5,...,F8,using the elegant method pioneered by Lucas[47,p.302],Kraitchik[40,p.135]and Lehmer[42,p.330].To prove p prime by this method,it is necessary to completely factor p?1and?nd a primitive root(mod p).The method is applied recursively to large prime factors of p?1.

Similar certi?cates can be given for the factors p49and p99of F9,using Crandall’s factorizations[44]of p49?1and p99?1:

p49?1=211·19·47·82488781·1143290228161321·43226490359557706629, p99?1=211·1129·26813·40644377·17338437577121·p68,and

p68?1=2·33·13·1531·173897·1746751·12088361983·

1392542208042011209·3088888502468305782559.

In these three cases the least primitive roots are3.

FACTORIZATION OF FERMAT NUMBERS BY ECM447 For the penultimate factor p40of F10,the least primitive root is5,and we have p40?1=212·3·5639·8231·433639·18840862799165386003967,

p40+1=2·2887·52471477·31186157593·493177304177011507.

The same method cannot be applied to prove primality of the largest prime factors of F10and F11,because we have only incomplete factorizations: p252?1=213·3·13·23·29·6329·760347109·

211898520832851652018708913943317·

9409853205696664168149671432955079744397·c158, p252+1=2·24407·507702159469·c235,

p564?1=213·139·1847·32488628503·1847272285831883·

92147345984208191·23918760924164258488261·c489, p564+1=2·32·65231833·c555.

We can apply Selfridge’s“Cube Root Theorem”[21,Theorem11]to p252,since p252?1=F·c158,where F>2×1093is completely factored,p252<2F3+2F, and the other conditions of the Cube Root Theorem are easily veri?ed.Thus,p252 is prime,and the factorization of F10is complete.

The large factor p564of F11was proved prime by Morain(in June1988)using a distributed version of his ecpp program[54,p.13].We have used the publicly available version of ecpp,which implements the“elliptic curve”method of Atkin and Morain[1],to con?rm this result.Version V3.4.1of ecpp,running on a60Mhz SuperSparc,established the primality of p564in28hours.It took only one hour to prove p252prime by the same method.Primality“certi?cates”are available[15]. They can be checked using a separate program xcheckcertif.

10.When to use ECM,and prospects for F12

When factoring large integers by ECM we do not usually know the size of the factors in advance.Thus,it is impossible to estimate how long ECM will require. In contrast,the running times of the MPQS and GNFS methods can be predicted fairly well,because they depend mainly on the size of the number being factored, and not on the size of the(unknown)factors,see[3,32,60].An important question is how long to spend on ECM before switching to a more predictable method such as MPQS/GNFS.This question is considered in[71,§7],but our approach is di?erent.

Theorem3of Vershik[73]says(approximately)that the ratios log q/log p of logarithms of neighboring large prime divisors q,p(q

448R.P.BRENT

For example,if we are factoring N 10100and U 0is such that q 1030,then we could assume that the unknown factor p lies in the interval 1030,1050 and that 1/log 10p is uniformly distributed in the corresponding interval (1/50,1/30).The probability P can now be estimated,using the results of §4.4,if we assume that the parameters B 1and B 2are chosen optimally to ?nd factors of size close to q .The estimate might,for example,be P 1/(cU 0),where c 9.

If the predicted running time of MPQS/GNFS exceeds 1/P units,then it is worthwhile to continue with ECM for a little longer.If ECM is unsuccessful,we repeat the procedure of estimating P .Eventually,either a factor will be found by ECM or the estimate of P will become so small that a switch to MPQS/GNFS is in-dicated.If a factor p is found by ECM,then the quotient N/p is either prime (so the factorization is complete)or much smaller than the original composite number N ,and hence much more easily factored by MPQS/GNFS.

Our approach is reasonable in the limiting case N →∞,because the assumption that 1/log p is uniformly distributed in (0,1/log q )gives a positive estimate for P .For example,replacing N 10100by N F 15in the example above multiplies the constant c by a factor of about 2.5=(1/30)/(1/30?1/50).

For the Fermat numbers F n ,12≤n ≤15,the predicted probability of success for ECM is low,but the predicted running time of other methods is so large that it is rational to continue trying ECM.There is no practical alternative except the old method of trial division.

Table 4.Second-largest prime factors of F n n

7891011ρ20.980.450.820.270.06

Although Fermat numbers are not random integers,it is interesting to compute ρ2(α)for α=log F n /log p 2,where p 2is the second-largest prime factor of F n and ρ2(α)is de?ned by (11).The values for n =7,...,11are given in Table 4.For large random integers,we expect ρ2(α)to be uniformly distributed (see §4.1).We see that F 11has a surprisingly small second-largest factor,and F 7has a surprisingly large second-largest factor.The second-largest factors of F 8,F 9and F 10are not exceptionally small or large.

The probability that a random integer N close to F 12has second-largest prime factor p 2<1040is 0.059.F 12has ?ve known prime factors (see §1).Harvey Dubner and the author have tried more than 2200curves with B 1≥106,in an attempt to factor F 12,without ?nding more than the ?ve known prime factors.Thus,from Table 2and (24),we can be reasonably con?dent that the sixth-smallest prime factor of F 12is at least 1030;a smaller factor would have been found with probability greater than 0.99.An indication of the likely size of the sixth-smallest prime factor can be obtained from Vershik’s result [73,Thm.3],which is paraphrased above.

The complete factorization of F 12may have to wait for a signi?cant improve-ment in integer factorization algorithms or the physical construction of a quantum computer capable of running Shor’s algorithm [68].

References

[1] A.O.L.Atkin and F.Morain,Elliptic curves and primality proving,https://www.wendangku.net/doc/7b14130250.html,p.61

(1993),29–68.Programs available from ftp://ftp.inria.fr/INRIA/ecpp.V3.4.1.tar.Z .MR 93m:11136

高二《甜美纯净的女声独唱》教案

高二《甜美纯净的女声独唱》教案 一、基本说明 教学内容 1）教学内容所属模块：歌唱 2）年级：高二 3）所用教材出版单位：湖南文艺出版社 4）所属的章节：第三单元第一节 5）学时数： 45 分钟 二、教学设计 1、教学目标： ①、在欣赏互动中感受女声的音域及演唱风格，体验女声的音色特点。 ②、在欣赏互动中，掌握美声、民族、通俗三种唱法的特点，体验其魅力。 ③、让学生能够尝试用不同演唱风格表现同一首歌。 ④、通过学唱歌曲培养学生热爱祖国、热爱生活的激情。 2、教学重点： ①、掌握女高音、女中音的音域和演唱特点。 ②、掌握美声、民族、通俗三种方法演唱风格。 3、教学难点： ①、学生归纳不同唱法的特点与风格。

②、学生尝试用不同演唱风格表现同一首歌。 3、设计思路 《普通高中音乐课程标准》指出：“音乐课的教学过程就是音乐的艺术实践过程。”《甜美纯净的女声独唱》作为《魅力四射的独唱舞台》单元的第一课，是让学生在丰富多彩的歌唱艺术形式中感受出女声独唱以其优美纯净的声音特点而散发出独特的魅力。为此，本课从身边熟悉的人物和情景入手，激发学生学习兴趣，把教学重心放在艺术实践中，让学生在欣赏、学习不同的歌唱风格中，培养自己的综合欣赏能力及歌唱水平。在教学过程中让学生体会不同风格的甜美纯净女声的内涵，感知优美纯净的声音特点而散发出的独特魅力，学会多听、多唱，掌握一定的歌唱技巧，提高自己的演唱水平。为实现以上目标，本人将新课标“过程与方法”中的“体验、比较、探究、合作”四个具体目标贯穿全课，注重学生的个人感受和独特见解，鼓励学生的自我意识与创新精神，强调探究、强调实践，将教学过程变为整合、转化间接经验为学生直接经验的过程，让学生亲身去感悟、去演唱，并力求改变现在高中学生普遍只关注流行歌曲的现状，让学生自己确定最适合自己演唱的方法，自我发现、自我欣赏，充分展示自己的的声音魅力。 三、教学过程 教学环节及时间教师活动学生活动设计意图

初中语文古文赏析曹操《短歌行》赏析(林庚)

教育资料 《短歌行》 《短歌行》赏析(林庚) 曹操这一首《短歌行》是建安时代杰出的名作，它代表着人生的两面，一方面是人生的忧患，一方面是人生的欢乐。而所谓两面也就是人生的全面。整个的人生中自然含有一个生活的态度，这就具体地表现在成为《楚辞》与《诗经》传统的产儿。它一方面不失为《楚辞》中永恒的追求，一方面不失为一个平实的生活表现，因而也就为建安诗坛铺平了道路。 这首诗从“对酒当歌，人生几何”到“但为君故，沉吟至今”，充分表现着《楚辞》里的哀怨。一方面是人生的无常，一方面是永恒的渴望。而“呦呦鹿鸣”以下四句却是尽情的欢乐。你不晓得何以由哀怨这一端忽然会走到欢乐那一端去，转折得天衣无缝，仿佛本来就该是这么一回事似的。这才是真正的人生的感受。这一段如是，下一段也如是。“明明如月，何时可掇?忧从中来，不可断绝。越陌度阡，枉用相存。契阔谈宴，心念旧恩。月明星稀，乌鹊南飞。绕树三匝，何枝可依。”缠绵的情调，把你又带回更深的哀怨中去。但“山不厌高，海不厌深”，终于走入“周公吐哺，天下归心”的结论。上下两段是一个章法，但是你并不觉得重复，你只觉得卷在悲哀与欢乐的旋涡中，不知道什么时候悲哀没有了，变成欢乐，也不知道什么时候欢乐没有了，又变成悲哀，这岂不是一个整个的人生吗?把整个的人生表现在一个刹那的感觉上，又都归于一个最实在的生活上。“我有嘉宾，鼓瑟吹笙”，不正是当时的情景吗?“周公吐哺，天下归心”，不正是当时的信心吗? “青青子衿”到“鼓瑟吹笙”两段连贯之妙，古今无二。《诗经》中现成的句法一变而有了《楚辞》的精神，全在“沉吟至今”的点窜，那是“青青子衿”的更深的解释，《诗经》与《楚辞》因此才有了更深的默契，从《楚辞》又回到《诗经》，这样与《鹿鸣》之诗乃打成一片，这是一个完满的行程，也便是人生旅程的意义。“月明星稀”何以会变成“山不厌高，海不厌深”?几乎更不可解。莫非由于“明月出天山”，“海上生明月”吗?古辞说：“枯桑知天风，海水知天寒”，枯桑何以知天风，因为它高；海水何以知天寒，因为它深。唐人诗“一叶落知天下秋”，我们对于宇宙万有正应该有一个“知”字。然则既然是山，岂可不高?既然是海，岂可不深呢?“并刀如水，吴盐胜雪”，既是刀，就应该雪亮；既是盐，就应该雪白，那么就不必问山与海了。 山海之情，成为漫漫旅程的归宿，这不但是乌鹊南飞，且成为人生的思慕。山既尽其高，海既尽其深。人在其中乃有一颗赤子的心。孟子主尽性，因此养成他浩然之气。天下所以归心，我们乃不觉得是一个夸张。 .

The way常见用法

The way 的用法 Ⅰ常见用法： 1)the way+ that 2)the way + in which（最为正式的用法） 3)the way + 省略（最为自然的用法） 举例：I like the way in which he talks. I like the way that he talks. I like the way he talks. Ⅱ习惯用法： 在当代美国英语中，the way用作为副词的对格，“the way+ 从句”实际上相当于一个状语从句来修饰整个句子。 1)The way =as I am talking to you just the way I’d talk to my own child. He did not do it the way his friends did. Most fruits are naturally sweet and we can eat them just the way they are—all we have to do is to clean and peel them. 2）The way= according to the way/ judging from the way The way you answer the question, you are an excellent student. The way most people look at you, you’d think trash man is a monster. 3）The way =how/ how much No one can imagine the way he missed her. 4）The way =because

适合女生KTV唱的100首好听的歌

适合女生KTV唱的100首好听的歌别吝色你的嗓音很好学 1、偏爱----张芸京 2、阴天----莫文蔚 3、眼泪----范晓萱 4、我要我们在一起---=范晓萱 5、无底洞----蔡健雅 6、呼吸----蔡健雅 7、原点----蔡健雅&孙燕姿 8、我怀念的----孙燕姿 9、不是真的爱我----孙燕姿 10、我也很想他----孙燕姿 11、一直很安静----阿桑 12、让我爱----阿桑 13、错过----梁咏琪 14、爱得起----梁咏琪 15、蓝天----张惠妹 16、记得----张惠妹 17、简爱----张惠妹 18、趁早----张惠妹 19、一念之间----戴佩妮 20、两难----戴佩妮 21、怎样----戴佩妮 22、一颗心的距离----范玮琪 23、我们的纪念日----范玮琪 24、启程----范玮琪 25、最初的梦想----范玮琪 26、是非题----范玮琪 27、你是答案----范玮琪 28、没那么爱他----范玮琪 29、可不可以不勇敢----范玮琪 30、一个像夏天一个像秋天----范玮琪 31、听，是谁在唱歌----刘若英 32、城里的月光----许美静 33、女人何苦为难女人----辛晓琪 34、他不爱我----莫文蔚 35、你是爱我的----张惠妹 36、同类----孙燕姿 37、漩涡----孙燕姿 38、爱上你等于爱上寂寞----那英 39、梦醒了----那英 40、出卖----那英 41、梦一场----那英 42、愿赌服输----那英

43、蔷薇----萧亚轩 44、你是我心中一句惊叹----萧亚轩 45、突然想起你----萧亚轩 46、类似爱情----萧亚轩 47、Honey----萧亚轩 48、他和他的故事----萧亚轩 49、一个人的精彩----萧亚轩 50、最熟悉的陌生人----萧亚轩 51、想你零点零一分----张靓颖 52、如果爱下去----张靓颖 53、我想我是你的女人----尚雯婕 54、爱恨恢恢----周迅 55、不在乎他----张惠妹 56、雪地----张惠妹 57、喜欢两个人----彭佳慧 58、相见恨晚----彭佳慧 59、囚鸟----彭羚 60、听说爱情回来过----彭佳慧 61、我也不想这样----王菲 62、打错了----王菲 63、催眠----王菲 64、执迷不悔----王菲 65、阳宝----王菲 66、我爱你----王菲 67、闷----王菲 68、蝴蝶----王菲 69、其实很爱你----张韶涵 70、爱情旅程----张韶涵 71、舍得----郑秀文 72、值得----郑秀文 73、如果云知道----许茹芸 74、爱我的人和我爱的人----裘海正 75、谢谢你让我这么爱你----柯以敏 76、陪我看日出----蔡淳佳 77、那年夏天----许飞 78、我真的受伤了----王菀之 79、值得一辈子去爱----纪如璟 80、太委屈----陶晶莹 81、那年的情书----江美琪 82、梦醒时分----陈淑桦 83、我很快乐----刘惜君 84、留爱给最相爱的人----倪睿思 85、下一个天亮----郭静 86、心墙----郭静

高中语文文言文曹操《短歌行(对酒当歌)》原文、翻译、赏析

曹操《短歌行【对酒当歌】》原文、翻译、赏析译文 原文 面对美酒应该高歌，人生短促日月如梭。对酒当歌，人生几何？ 好比晨露转瞬即逝，失去的时日实在太多！譬如朝露，去日苦多。 席上歌声激昂慷慨，忧郁长久填满心窝。慨当以慷，忧思难忘。 靠什么来排解忧闷？唯有狂饮方可解脱。何以解忧？唯有杜康。 那穿着青领（周代学士的服装）的学子哟，你们令我朝夕思慕。青青子衿，悠悠我心。 正是因为你们的缘故，我一直低唱着《子衿》歌。但为君故，沉吟至今。 阳光下鹿群呦呦欢鸣，悠然自得啃食在绿坡。呦呦鹿鸣，食野之苹。 一旦四方贤才光临舍下，我将奏瑟吹笙宴请宾客。我有嘉宾，鼓瑟吹笙。 当空悬挂的皓月哟，你运转着，永不停止；明明如月，何时可掇？ 我久蓄于怀的忧愤哟，突然喷涌而出汇成长河。忧从中来，不可断绝。 远方宾客踏着田间小路，一个个屈驾前来探望我。越陌度阡，枉用相存。 彼此久别重逢谈心宴饮，争着将往日的情谊诉说。契阔谈讌，心念旧恩。 明月升起，星星闪烁，一群寻巢乌鹊向南飞去。月明星稀，乌鹊南飞。 绕树飞了三周却没敛绕树三匝，何枝

翅，哪里才有它们栖身之 所？ 可依？ 高山不辞土石才见巍 峨，大海不弃涓流才见壮阔。（比喻用人要“唯才是举”，多多益善。）山不厌高，水不厌深。 只有像周公那样礼待贤 才（周公见到贤才，吐出口 中正在咀嚼的食物，马上接 待。《史记》载周公自谓： “一沐三握发，一饭三吐哺， 犹恐失天下之贤。”），才 能使天下人心都归向我。 周公吐哺，天 赏析 曹操是汉末杰出的政治家、军事家和文学家，他雅好诗章，好作乐府歌辞，今存诗22首，全是乐府诗。曹操的乐府诗多描写他本人的政治主张和统一天下的雄心壮志。如他的《短歌行》，充分表达了诗人求贤若渴以及统一天下的壮志。 《短歌行》是政治性很强的诗作，主要是为曹操当时所实行的政治路线和政策策略服务的，但是作者将政治内容和意义完全熔铸在浓郁的抒情意境之中，全诗充分发挥了诗歌创作的特长，准确而巧妙地运用了比兴手法，寓理于情，以情感人。诗歌无论在思想内容还是在艺术上都取得了极高的成就，语言质朴，立意深远，气势充沛。这首带有建安时代"志深比长""梗概多气"的时代特色的《短歌行》，读后不觉思接千载，荡气回肠，受到强烈的感染。 对酒当歌，人生几何？ 譬如朝露，去日苦多。 慨当以慷，幽思难忘。 何以解忧，唯有杜康。 青青子衿，悠悠我心。 但为君故，沈吟至今。 呦呦鹿鸣，食野之苹。 我有嘉宾，鼓瑟吹笙。 明明如月，何时可掇？ 忧从中来，不可断绝。 越陌度阡，枉用相存。 契阔谈，心念旧恩。 月明星稀，乌鹊南飞， 绕树三匝，何枝可依？ 山不厌高，海不厌深， 周公吐哺，天下归心。 《短歌行》是汉乐府的旧题，属于《相和歌?平调曲》。这就是说它本来是一个乐曲的名称，这种乐曲怎么唱法，现在当然是不知道了。但乐府《相和歌?平调曲》中除了《短歌行》还有《长歌行》，唐代吴兢《乐府古题要解》引证古诗“长歌正激烈”，魏文帝曹丕《燕歌行》“短歌微吟不能长”和晋代傅玄《艳歌行》“咄来长歌续短歌”等句，认为“长歌”、“短

外国文学名著鉴赏期末论文

外国文学名著鉴赏期末论文院—系：数学学院 科目：外国文学名著鉴赏（期末论文）班级： 08级数学与应用数学A班 姓名：沈铁 学号： 200805050149 上课时段：周五晚十、十一节课

奋斗了，才有出路 ——读《鲁宾逊漂游记》有感小说《鲁宾逊漂游记》一直深受人们的喜爱。读完这篇小说，使我对人生应该有自己的一个奋斗历程而受益匪浅。当一个人已经处于绝境的时候，还能够满怀信心的去面对和挑战生活，实在是一种可贵的精神。他使我认识到，人无论何时何地，不管遇到多大的困难，都不能被困难所吓倒，我们要勇敢的面对困难，克服困难，始终保持一种积极向上、乐观的心态去面对。在当今社会只有努力去奋斗，才会有自己的出路！ 其实现在的很多人都是那些遇到困难就退缩，不敢勇敢的去面对它。不仅如此，现在很多人都是独生子女，很多家长视子女为掌上明珠，不要说是冒险了，就连小小的家务活也不让孩子做，天天总是说：“我的小宝贝啊，你读好书就行了，其它的爸爸妈妈做就可以了。”读书固然重要，但生活中的小事也不能忽略。想一想，在荒无人烟的孤岛上，如果你连家务活都不会做，你能在那里生存吗？读完这部著作后，我不禁反问自己：“如果我像书中的鲁宾逊那样在大海遭到风暴，我能向他那样与风暴搏斗，最后逃离荒岛得救吗？恐怕我早已经被大海所淹没；如果我漂流到孤岛，能活几天？我又能干些什么？我会劈柴吗？会打猎做饭吗？我连洗洗自己的衣服还笨手笨脚的。”我们应该学习鲁宾逊这种不怕困难的精神，无论何时何地都有坚持地活下去，哪怕只有一线希望也要坚持到底，决不能放弃！我们要像鲁宾

逊那样有志气、有毅力、爱劳动，凭自己的双手创造财富，创造奇迹，取得最后的胜利。这样的例子在我们的生活中屡见不鲜。 《史记》的作者司马迁含冤入狱，可它依然在狱中完成《史记》一书，他之所以能完成此书，靠的也是他心中那顽强的毅力，永不放弃的不断努力的精神。著名作家爱迪生从小就生活在一个贫困的家庭中，可是他从小就表现出了科学方面的天赋。长大后爱迪生着力于电灯的发明与研究，他经过了九百多次的失败，可它依然没有放弃，不断努力，最后终于在第一千次实验中取得了成功。 鲁宾逊在岛上生活了二十八年，他面对了各种各样的困难和挫折，克服了许多常人无法想象的困难，自己动手，丰衣足食，以惊人的毅力，顽强的活了下来。他自从大船失事后，找了一些木材，在岛上盖了一间房屋，为防止野兽，还在房子周围打了木桩，来到荒岛，面对着的首要的就是吃的问题，船上的东西吃完以后，鲁宾逊开始打猎，有时可能会饿肚子，一是他决定播种，几年后他终于可以吃到自己的劳动成果，其实学习也是这样，也有这样一个循序渐进的过程，现在的社会，竞争无处不在，我们要懂得只有付出才会有收获，要勇于付出，在战胜困难的同时不断取得好成绩。要知道只有付出，才会有收获。鲁宾逊在失败后总结教训，终于成果；磨粮食没有石磨，他就用木头代替；没有筛子，就用围巾。鲁宾逊在荒岛上解决了自己的生存难题，面对人生挫折，鲁宾逊的所作所为充分显示了他坚毅的性格和顽强的精神。同样我们在学习上也可以做一些创新，养成一种创新精神，把鲁宾逊在荒岛，不畏艰险，不怕失败挫折，艰苦奋斗的精

The way的用法及其含义(二)

The way的用法及其含义（二） 二、the way在句中的语法作用 the way在句中可以作主语、宾语或表语： 1.作主语 The way you are doing it is completely crazy.你这个干法简直发疯。 The way she puts on that accent really irritates me. 她故意操那种口音的样子实在令我恼火。The way she behaved towards him was utterly ruthless. 她对待他真是无情至极。 Words are important, but the way a person stands, folds his or her arms or moves his or her hands can also give us information about his or her feelings. 言语固然重要,但人的站姿,抱臂的方式和手势也回告诉我们他(她)的情感。 2.作宾语 I hate the way she stared at me.我讨厌她盯我看的样子。 We like the way that her hair hangs down.我们喜欢她的头发笔直地垂下来。 You could tell she was foreign by the way she was dressed. 从她的穿著就可以看出她是外国人。 She could not hide her amusement at the way he was dancing. 她见他跳舞的姿势，忍俊不禁。 3.作表语 This is the way the accident happened.这就是事故如何发生的。 Believe it or not, that's the way it is. 信不信由你, 反正事情就是这样。 That's the way I look at it, too. 我也是这么想。 That was the way minority nationalities were treated in old China. 那就是少数民族在旧中

曹操《短歌行》其二翻译及赏析

曹操《短歌行》其二翻译及赏析 引导语：曹操(155—220)，字孟德，小名阿瞒，《短歌行 二首》 是曹操以乐府古题创作的两首诗， 第一首诗表达了作者求贤若渴的心 态，第二首诗主要是曹操向内外臣僚及天下表明心迹。 短歌行 其二 曹操 周西伯昌，怀此圣德。 三分天下，而有其二。 修奉贡献，臣节不隆。 崇侯谗之，是以拘系。 后见赦原，赐之斧钺，得使征伐。 为仲尼所称，达及德行， 犹奉事殷，论叙其美。 齐桓之功，为霸之首。 九合诸侯，一匡天下。 一匡天下，不以兵车。 正而不谲，其德传称。 孔子所叹，并称夷吾，民受其恩。 赐与庙胙，命无下拜。 小白不敢尔，天威在颜咫尺。 晋文亦霸，躬奉天王。 受赐圭瓒，钜鬯彤弓， 卢弓矢千，虎贲三百人。 威服诸侯，师之所尊。 八方闻之，名亚齐桓。 翻译 姬昌受封为西伯，具有神智和美德。殷朝土地为三份，他有其中两分。 整治贡品来进奉，不失臣子的职责。只因为崇侯进谗言，而受冤拘禁。 后因为送礼而赦免， 受赐斧钺征伐的权利。 他被孔丘称赞， 品德高尚地位显。 始终臣服殷朝帝王，美名后世流传遍。齐桓公拥周建立功业，存亡继绝为霸 首。

聚合诸侯捍卫中原，匡正天下功业千秋。号令诸侯以匡周室，主要靠的不是 武力。 行为磊落不欺诈，美德流传于身后。孔子赞美齐桓公，也称赞管仲。 百姓深受恩惠，天子赐肉与桓公，命其无拜来接受。桓公称小白不敢，天子 威严就在咫尺前。 晋文公继承来称霸，亲身尊奉周天王。周天子赏赐丰厚，仪式隆重。 接受玉器和美酒，弓矢武士三百名。晋文公声望镇诸侯，从其风者受尊重。 威名八方全传遍，名声仅次于齐桓公。佯称周王巡狩，招其天子到河阳，因 此大众议论纷纷。 赏析 《短歌行》 (“周西伯昌”)主要是曹操向内外臣僚及天下表明心 迹，当他翦灭群凶之际，功高震主之时，正所谓“君子终日乾乾，夕惕若 厉”者，但东吴孙权却瞅准时机竟上表大说天命而称臣，意在促曹操代汉 而使其失去“挟天子以令诸侯”之号召， 故曹操机敏地认识到“ 是儿欲据吾著炉上郁!”故曹操运筹谋略而赋此《短歌行 ·周西伯 昌》。 西伯姬昌在纣朝三分天下有其二的大好形势下， 犹能奉事殷纣， 故孔子盛称 “周之德， 其可谓至德也已矣。 ”但纣王亲信崇侯虎仍不免在纣王前 还要谗毁文王，并拘系于羑里。曹操举此史实，意在表明自己正在克心效法先圣 西伯姬昌，并肯定他的所作所为，谨慎惕惧，向来无愧于献帝之所赏。 并大谈西伯姬昌、齐桓公、晋文公皆曾受命“专使征伐”。而当 今天下时势与当年的西伯、齐桓、晋文之际颇相类似，天子如命他“专使 征伐”以讨不臣，乃英明之举。但他亦效西伯之德，重齐桓之功，戒晋文 之诈。然故作谦恭之辞耳，又谁知岂无更讨封赏之意乎 ?不然建安十八年(公元 213 年)五月献帝下诏曰《册魏公九锡文》，其文曰“朕闻先王并建明德， 胙之以土，分之以民，崇其宠章，备其礼物，所以藩卫王室、左右厥世也。其在 周成，管、蔡不静，惩难念功，乃使邵康公赐齐太公履，东至于海，西至于河， 南至于穆陵，北至于无棣，五侯九伯，实得征之。 世祚太师，以表东海。爰及襄王，亦有楚人不供王职，又命晋文登为侯伯， 锡以二辂、虎贲、斧钺、禾巨 鬯、弓矢，大启南阳，世作盟主。故周室之不坏， 系二国是赖。”又“今以冀州之河东、河内、魏郡、赵国、中山、常 山，巨鹿、安平、甘陵、平原凡十郡，封君为魏公。锡君玄土，苴以白茅，爰契 尔龟。”又“加君九锡，其敬听朕命。” 观汉献帝下诏《册魏公九锡文》全篇，尽叙其功，以为其功高于伊、周，而 其奖却低于齐、晋，故赐爵赐土，又加九锡，奖励空前。但曹操被奖愈高，心内 愈忧。故曹操在曾早在五十六岁写的《让县自明本志令》中谓“或者人见 孤强盛， 又性不信天命之事， 恐私心相评， 言有不逊之志， 妄相忖度， 每用耿耿。

2008年浙师大《外国文学名著鉴赏》期末考试答案

（一）文学常识 一、古希腊罗马 1．（1）宙斯(罗马神话称为朱庇特)，希腊神话中最高的天神，掌管雷电云雨，是人和神的主宰。 （2）阿波罗，希腊神话中宙斯的儿子，主管光明、青春、音乐、诗歌等，常以手持弓箭的少年形象出现。 （3）雅典那，希腊神话中的智慧女神，雅典城邦的保护神。 （4）潘多拉，希腊神话中的第一个女人，貌美性诈。私自打开了宙斯送她的一只盒子，里面装的疾病、疯狂、罪恶、嫉妒等祸患，一齐飞出，只有希望留在盒底，人间因此充满灾难。“潘多拉的盒子”成为“祸灾的来源”的同义语。 （5）普罗米修斯，希腊神话中造福人间的神。盗取天火带到人间，并传授给人类多种手艺，触怒宙斯，被锁在高加索山崖，受神鹰啄食，是一个反抗强暴、不惜为人类牺牲一切的英雄。 （6）斯芬克司，希腊神话中的狮身女怪。常叫过路行人猜谜，猜不出即将行人杀害；后因谜底被俄底浦斯道破，即自杀。后常喻“谜”一样的人物。与埃及狮身人面像同名。 2．荷马，古希腊盲诗人。主要作品有《伊利亚特》和《奥德赛》，被称为荷马史诗。《伊利亚特》叙述十年特洛伊战争。《奥德赛》写特洛伊战争结束后，希腊英雄奥德赛历险回乡的故事。马克思称赞它“显示出永久的魅力”。 3．埃斯库罗斯，古希腊悲剧之父，代表作《被缚的普罗米修斯》。6．阿里斯托芬，古希腊“喜剧之父”代表作《阿卡奈人》。 4．索福克勒斯，古希腊重要悲剧作家，代表作《俄狄浦斯王》。5．欧里庇得斯，古希腊重要悲剧作家，代表作《美狄亚》。 二、中世纪文学 但丁，意大利人，伟大诗人，文艺复兴的先驱。恩格斯称他是“中世纪的最后一位诗人，同时又是新时代的最初一位诗人”。主要作品有叙事长诗《神曲》，由地狱、炼狱、天堂三部分组成。《神曲》以幻想形式，写但丁迷路，被人导引神游三界。在地狱中见到贪官污吏等受着惩罚，在净界中见到贪色贪财等较轻罪人，在天堂里见到殉道者等高贵的灵魂。 三、文艺复兴时期 1．薄迦丘意大利人短篇小说家，著有《十日谈》拉伯雷，法国人，著《巨人传》塞万提斯，西班牙人,著《堂?吉诃德》。 2．莎士比亚，16-17世纪文艺复兴时期英国伟大的剧作家和诗人，主要作品有四大悲剧——《哈姆雷特》、《奥赛罗》《麦克白》、《李尔王》，另有悲剧《罗密欧与朱丽叶》等，喜剧有《威尼斯商人》《第十二夜》《皆大欢喜》等，历史剧有《理查二世》、《亨利四世》等。马克思称之为“人类最伟大的戏剧天才”。 四、17世纪古典主义 9．笛福，17-18世纪英国著名小说家，被誉为“英国和欧洲小说之父”，主要作品《鲁滨逊漂流记》，是英国第一部现实主义长篇小说。10．弥尔顿，17世纪英国诗人，代表作：长诗《失乐园》，《失乐园》，表现了资产阶级清教徒的革命理想和英雄气概。 25．拉伯雷，16世纪法国作家，代表作：长篇小说《巨人传》。 26．莫里哀，法国17世纪古典主义文学最重要的作家，法国古典主义喜剧的创建者，主要作品为《伪君子》《悭吝人》（主人公叫阿巴公）等喜剧。 五、18世纪启蒙运动 1）歌德，德国文学最高成就的代表者。主要作品有书信体小说《少年维特之烦恼》，诗剧《浮士德》。 11．斯威夫特，18世纪英国作家，代表作：《格列佛游记》，以荒诞的情节讽刺了英国现实。 12．亨利·菲尔丁，18世纪英国作家，代表作：《汤姆·琼斯》。 六、19世纪浪漫主义 （1拜伦， 19世纪初期英国伟大的浪漫主义诗人，代表作为诗体小说《唐璜》通过青年贵族唐璜的种种经历，抨击欧洲反动的封建势力。《恰尔德。哈洛尔游记》 （2雨果，伟大作家，欧洲19世纪浪漫主义文学最卓越的代表。主要作品有长篇小说《巴黎圣母院》、《悲惨世界》、《笑面人》、《九三年》等。《悲惨世界》写的是失业短工冉阿让因偷吃一片面包被抓进监狱，后改名换姓，当上企业主和市长，但终不能摆脱迫害的故事。《巴黎圣母院》 弃儿伽西莫多，在一个偶然的场合被副主教克洛德.孚罗洛收养为义子，长大后有让他当上了巴黎圣母院的敲钟人。他虽然十分丑陋而且有多种残疾，心灵却异常高尚纯洁。 长年流浪街头的波希米亚姑娘拉.爱斯梅拉达，能歌善舞，天真貌美而心地淳厚。青年贫诗人尔比埃尔.甘果瓦偶然同她相遇，并在一个更偶然的场合成了她名义上的丈夫。很有名望的副教主本来一向专心于"圣职"，忽然有一天欣赏到波希米亚姑娘的歌舞，忧千方百计要把她据为己有，对她进行了种种威胁甚至陷害，同时还为此不惜玩弄卑鄙手段，去欺骗利用他的义子伽西莫多和学生甘果瓦。眼看无论如何也实现不了占有爱斯梅拉达的罪恶企图，最后竟亲手把那可爱的少女送上了绞刑架。 另一方面，伽西莫多私下也爱慕着波希米亚姑娘。她遭到陷害，被伽西莫多巧计救出，在圣母院一间密室里避难，敲钟人用十分纯朴和真诚的感情去安慰她，保护她。当她再次处于危急中时，敲钟人为了援助她，表现出非凡的英勇和机智。而当他无意中发现自己的"义父"和"恩人"远望着高挂在绞刑架上的波希米亚姑娘而发出恶魔般的狞笑时，伽西莫多立即对那个伪善者下了最后的判决，亲手把克洛德.孚罗洛从高耸入云的钟塔上推下，使他摔的粉身碎骨。 （3司汤达，批判现实主义作家。代表作《红与黑》，写的是不满封建制度的平民青年于连，千方百计向上爬，最终被送上断头台的故事。“红”是将军服色，指“入军界”的道路；“黑”是主教服色，指当神父、主教的道路。 14．雪莱，19世纪积极浪漫主义诗人，欧洲文学史上最早歌颂空想社会主义的诗人之一，主要作品为诗剧《解放了的普罗米修斯》，抒情诗《西风颂》等。 15．托马斯·哈代，19世纪英国作家，代表作：长篇小说《德伯家的苔丝》。 16．萨克雷，19世纪英国作家，代表作：《名利场》 17．盖斯凯尔夫人，19世纪英国作家，代表作：《玛丽·巴顿》。 18．夏洛蒂?勃朗特，19世纪英国女作家，代表作：长篇小说《简?爱》19艾米丽?勃朗特，19世纪英国女作家，夏洛蒂?勃朗特之妹，代表作：长篇小说《呼啸山庄》。 20．狄更斯，19世纪英国批判现实主义文学的重要代表，主要作品为长篇小说《大卫?科波菲尔》、《艰难时世》《双城记》《雾都孤儿》。21．柯南道尔，19世纪英国著名侦探小说家，代表作品侦探小说集《福尔摩斯探案》是世界上最著名的侦探小说。 七、19世纪现实主义 1、巴尔扎克，19世纪上半叶法国和欧洲批判现实主义文学的杰出代表。主要作品有《人间喜剧》，包括《高老头》、《欧也妮·葛朗台》、《贝姨》、《邦斯舅舅》等。《人间喜剧》是世界文学中规模最宏伟的创作之一，也是人类思维劳动最辉煌的成果之一。马克思称其“提供了一部法国社会特别是巴黎上流社会的卓越的现实主义历史”。

(完整版)the的用法

定冠词the的用法： 定冠词the与指示代词this ,that同源,有“那(这)个”的意思,但较弱,可以和一个名词连用,来表示某个或某些特定的人或东西. (1)特指双方都明白的人或物 Take the medicine.把药吃了. (2)上文提到过的人或事 He bought a house.他买了幢房子. I've been to the house.我去过那幢房子. (3)指世界上独一无二的事物 the sun ,the sky ,the moon, the earth (4)单数名词连用表示一类事物 the dollar 美元 the fox 狐狸 或与形容词或分词连用,表示一类人 the rich 富人 the living 生者 (5)用在序数词和形容词最高级,及形容词等前面 Where do you live?你住在哪? I live on the second floor.我住在二楼. That's the very thing I've been looking for.那正是我要找的东西. (6)与复数名词连用,指整个群体 They are the teachers of this school.(指全体教师) They are teachers of this school.(指部分教师) (7)表示所有,相当于物主代词,用在表示身体部位的名词前 She caught me by the arm.她抓住了我的手臂. (8)用在某些有普通名词构成的国家名称,机关团体,阶级等专有名词前 the People's Republic of China 中华人民共和国 the United States 美国 (9)用在表示乐器的名词前 She plays the piano.她会弹钢琴. (10)用在姓氏的复数名词之前,表示一家人 the Greens 格林一家人(或格林夫妇) (11)用在惯用语中 in the day, in the morning... the day before yesterday, the next morning... in the sky... in the dark... in the end... on the whole, by the way...

2019-2020年高一音乐 甜美纯净的女声独唱教案

2019-2020年高一音乐甜美纯净的女声独唱教案 一、教学目标 1、认知目标：初步了解民族唱法、美声唱法、通俗唱法三种唱法的风格。 2、能力目标：通过欣赏部分女声独唱作品，学生能归纳总结出她们的演唱 风格和特点，并同时用三种不同风格演唱同一首歌曲。 3、情感目标：通过欣赏比较，对独唱舞台有更多元化的审美意识。 二、教学重点：学生能用三种不同风格演唱形式演唱同一首歌。 三、教学难点：通过欣赏部分女声独唱作品，学生能归纳总结出她们的演唱 风格和特点。 四、教学过程： （一）导入 1、播放第十三界全国青年歌手大奖赛预告片 （师）问：同学们对预告片中的歌手认识吗 （生）答： （师）问：在预告片中提出了几种唱法？ （生）答：有民族、美声、通俗以及原生态四种唱法，今天以女声独唱歌曲重点欣赏民族、美声、通俗唱法，希望通过欣赏同学们能总结出三种唱法的风格和特点。 （二）、音乐欣赏

1、通俗唱法 ①(师)问：同学们平常最喜欢唱那些女歌手的歌呢？能唱唱吗？ （可让学生演唱几句喜欢的歌，并鼓励） ②欣赏几首通俗音乐 视频一：毛阿敏《绿叶对根的情谊》片段、谭晶《在那东山顶上》片段、韩红《天路》片段、刘若英《后来》片段 视频二：超女《想唱就唱唱得响亮》 ①由学生总结出通俗音乐的特点 ②师总结并板书通俗音乐的特点：通俗唱法是在演唱通俗歌曲的基础上发展起来的，又称“流行唱法”。通俗歌曲是以通俗易懂、易唱易记、娱乐性强、便于流行而见长，它没有统一的规格和演唱技法的要求，比较强调歌唱者本人的自然嗓音和情绪的渲染，重视歌曲感情的表达。演唱上要求吐字清晰，音调流畅，表情真挚，带有口语化。 ③指出通俗音乐尚未形成系统的发声训练体系。其中用沙哑、干枯的音色“狂唱”和用娇柔、做作的姿态“嗲唱”，不属于声乐艺术的正道之物，应予以摒弃。 2、民族唱法 ①俗话说民族的才是世界的那么民族唱法的特点是什么呢？ ②欣赏彭丽媛《万里春色满人间》片段 鉴赏提示：这首歌是剧种女主角田玉梅即将走上刑场时的一段难度较大的咏叹调。

外国名著赏析论文

题目：浅析从简爱到女性的尊严和爱 学院工商学院 专业新闻学3 学号 姓名闫万里 学科外国文学名着赏析 [摘要] 十九世纪中期，英国伟大的女性存在主义先驱，着名作家夏洛蒂勃朗特创作出了她的代表作--《简爱》，当时轰动了整个文坛,它是一部具有浓厚浪漫主义色彩的现实主义小说，被认为是作者"诗意的生平"的写照。它在问世后的一百多年里，它始终保持着历史不败的艺术感染力。直到现在它的影响还继续存在。在作品的序幕、发展、高潮和结尾中，女主人公的叛逆、自由、平等、自尊、纯洁的个性都是各个重点章节的主旨，而这些主旨则在女主人公的爱情观中被展露的淋漓尽致，它们如同乌云上方的星汉，灼灼闪耀着光芒，照亮着后来的女性者们追求爱情的道路。? [关键词] 自尊个性独特新女性主义自由独立平等 《简爱》是一部带有自转色彩的长篇小说，它阐释了这样一个主题：人的价值=尊严+爱。从小就成长在一个充满暴力的环境中的简爱，经历了同龄人没有的遭遇。她要面对的是舅妈的毫无人性的虐待，表兄的凶暴专横和表姐的傲慢冷漠，尽管她尽力想“竭力赢得别人的好感”，但是事实告诉她这都是白费力气的，因此她发出了“不公平啊！--不公平！”的近乎绝望的呼喊。不公平的生长环境，使得简爱从小就向往平等、自由和爱，这些愿望在她后来的成长过程中表现无疑，

譬如在她的爱情观中的种种体现。? 1.桑菲尔德府? 谭波儿小姐因为出嫁，离开了洛伍德学校，同时也离开了简爱，这使简爱感觉到了“一种稳定的感觉，一切使我觉得洛伍德学校有点像我家的联想，全都随着她消失了”，她意识到：真正的世界是广阔的，一个充满希望和忧虑、激动和兴奋的变化纷呈的天地，正等待着敢于闯入、甘冒风险寻求人生真谛的人们。意识形态的转变促使着简爱走向更广阔的社会，接受社会的挑战，尽管她才只有十八岁。于是，简爱来到了桑菲尔德府，当了一名在当时地位不高的家庭教师。?桑菲尔德府使简爱感受到“这儿有想象中的完美无缺的家庭安乐气氛”，事实证明了她的预感的正确性，。从和简爱相见、相识到相爱的过程当中，简爱的那种叛逆精神、自强自尊的品质深深地征服了罗切斯特，而罗切斯特的优雅风度和渊博知识同样也征服了简爱。最初开始，简爱一直以为罗切斯特会娶高贵漂亮的英格拉姆为妻，她在和罗切斯特谈到婚姻时，曾经义正言辞的对罗切斯特说：“你以为因为我穷，低微，不美，矮小，就没有灵魂了吗？你想错了！我跟你一样有灵魂—也同样有一颗心！我现在不是凭着肉体凡胎跟你说话，而是我的心灵在和你的心灵说话，就好像我们都已经离开人世，两人平等地站在上帝面前—因为我们本来就是平等的。”这充分表现出简爱的叛逆，她这种维护妇女独立人格、主张婚姻独立自主以及男女平等的主张可以看成是他对整个人类社会自由平等的向往追求，罗切斯特正是爱上了她这样的独特个性，同时他也同样重复道：我们本来就是平等的。罗切斯特自始自终爱的是简爱的心灵—有着意志的力量，美德和纯洁的心灵，正是基于如此，简爱才真正的爱着罗切斯特。因为爱情是来不得半点虚假的，一方为另一方付出了真情的爱，假如得到对方的是虚情假意，那么这份爱

“the way+从句”结构的意义及用法

“tｈｅwａｙ+从句”结构的意义及用法 首先让我们来看下面这个句子: Ｒead the foｌloｗｉnｇpassagｅａnd talkａbout ｉt wi ｔh your classmaｔes．Try tｏｔeｌl whaｔyｏu thiｎk ｏf Tom aｎd ｏｆｔhe ｗay the chiｌｄrenｔrｅated ｈim. 在这个句子中，ｔhe waｙ是先行词,后面是省略了关系副词that或in whｉch的定语从句。 下面我们将叙述“the ｗaｙ+从句”结构的用法。 1.tｈe wａy之后，引导定语从句的关系词是tｈat而不是hoｗ,因此，<<现代英语惯用法词典＞＞中所给出的下面两个句子是错误的：Ｔhｉs is ｔｈeｗayｈowｉtｈａppened. This is the way how he ａlwａｙs treats me. 2．在正式语体中,thaｔ可被in which所代替;在非正式语体中，ｔhat则往往省略。由此我们得到theｗay后接定语从句时的三种模式：1) tｈe ｗaｙ＋ｔhａt-从句２）the way +ｉn whiｃh－从句3) the ｗay +从句 例如：Ｔｈe way(in whiｃh ，thａt) ｔhｅｓｅｃomｒade ｓloｏｋａｔｐrobｌems is wrong．这些同志看问题的方法

不对。 Ｔｈｅｗａy(that ,ｉn ｗhiｃh)yoｕ’ｒe doinｇit is comple ｔeｌy crａzy.你这么个干法,简直发疯。 Wｅａdmiｒｅd him for thｅｗay ｉｎｗhｉch he fａｃeｓdiｆficultieｓ． Waｌlａｃe ａｎd Ｄarwiｎｇreed ｏn the way ｉｎwhi ｃh ｄｉfｆｅrｅnt forms ｏf life had ｂegｕn.华莱士和达尔文对不同类型的生物是如何起源的持相同的观点。 Thｉs is ｔｈe ｗaｙ（tｈａｔ) hｅdｉd it. I lｉkeｄｔhe waｙ(ｔhat) ｓｈeｏｒganized ｔhe ｍeetｉng． 3.theｗay(tｈat)有时可以与hｏw(作“如何”解）通用。例如： That’s tｈe ｗaｙ(tｈaｔ) shｅspoke. = Tｈat’s how shｅspoke.

短歌行赏析介绍

短歌行赏析介绍 说道曹操， 大家一定就联想到三国那些烽火狼烟岁月吧。 但是曹操其实也是 一位文学 大家，今天就来分享《短歌行 》赏析。 《短歌行》短歌行》是汉乐府旧题，属于《相和歌辞·平调曲》。这就是说 它本来是一个乐曲名称。最初古辞已经失传。乐府里收集同名诗有 24 首，最早 是曹操这首。 这种乐曲怎么唱法， 现在当然是不知道。 但乐府 《相和歌·平调曲》 中除《短歌行》还有《长歌行》，唐代吴兢《乐府古题要解》引证古诗 “长歌正激烈”， 魏文帝曹丕 《燕歌行》 “短歌微吟不能长”和晋代傅玄 《艳 歌行》 “咄来长歌续短歌”等句， 认为“长歌”、 “短歌”是指“歌声有长短”。 我们现在也就只能根据这一点点材料来理解《短歌行》音乐特点。《短歌行》这 个乐曲，原来当然也有相应歌辞，就是“乐府古辞”，但这古辞已经失传。现在 所能见到最早《短歌行》就是曹操所作拟乐府《短歌行》。所谓“拟乐府”就是 运用乐府旧曲来补作新词，曹操传世《短歌行》共有两首，这里要介绍是其中第 一首。 这首《短歌行》主题非常明确，就是作者希望有大量人才来为自己所用。曹 操在其政治活动中，为扩大他在庶族地主中统治基础，打击反动世袭豪强势力， 曾大力强调“唯才是举”，为此而先后发布“求贤令”、“举士令”、“求逸才 令”等;而《短歌行》实际上就是一曲“求贤歌”、又正因为运用诗歌 形式，含有丰富抒情成分，所以就能起到独特感染作用，有力地宣传他所坚 持主张，配合他所颁发政令。 《短歌行》原来有“六解”(即六个乐段)，按照诗意分为四节来读。 “对酒当歌，人生几何?譬如朝露，去日苦多。慨当以慷，忧思难忘。何以 解忧，唯有杜康。” 在这八句中，作者强调他非常发愁，愁得不得。那么愁是什么呢?原来他是 苦于得不到众多“贤才”来同他合作， 一道抓紧时间建功立业。 试想连曹操这样 位高权重人居然在那里为“求贤”而发愁， 那该有多大宣传作用。 假如庶族地主 中真有“贤才”话， 看这些话就不能不大受感动和鼓舞。 他们正苦于找不到出路

外国文学名著赏析

外国文学名著赏析 ——对《哈姆雷特》与《堂吉诃德》人物形象及其现实意义的 分析 班级：学号：姓名： 摘要：《哈姆雷特》和《堂吉诃德》是文艺复兴时期涌现出来的一批比较先进的文学作品，通过对两部文学作品的阅读，我们不难发现两部作品所展现出来的人物形象都反映出了当时不同的社会现实，而且两部文学作品都表现出了浓厚的人文主义色彩，并且在当时也带来了不同的社会作用。堂吉诃德是塞万提斯塑造的一个为了打击骑士文学的文学形象，作者通过对堂吉诃德的描写，生动的说明了骑士文学给世人带来的负面影响，从而给骑士文学以致命的打击。莎士比亚笔下的哈姆雷特则是一个孤独的人文主义者，他以失败告终，哈姆雷特的失败向人们揭示了人文主义时代的悲剧。 Abstract: Hamlet a nd Don Quixote were the advanced literary in the Renaissance Period .After read the two novels, it is not difficult to find that different characters in these novels reflected different social problems. And they all expressed the ideas of humanism. These two images also brought different social functions at that time .Don Quixote is one of which Cervantes’s molds in order to attack the knight literature .According to the description of Don Quixote, vivid explain ed that knight literature brought a serious of bad influence to the human beings, thus gives the knight literature by the fatal attack. Hamlet is a lonely humanism, he is end in failure .His failure has indicated the tragedy which in the Humanism Era. 关键词：人文主义、哈姆雷特、人物形象、艺术特色、堂吉诃德、现实意义、悲剧 Key words:humanism; Hamlet; characters; art features; Don Quixote; realistic significance; tragedy 前言： 莎士比亚和塞万提斯都是文艺复兴时期伟大的戏剧家，作为戏剧艺术的大师，他们的作品都达到了世界文学的巅峰。《哈姆雷特》是莎士比亚最著名的悲剧之一，代表了莎士比亚的艺术成就，剧中莎士比亚塑造的著名人物哈姆雷特也被列入了世界文学的艺术画廊。塞万提斯是文艺复兴时期西班牙伟大的作家，在他创作的作品中，以《堂吉诃德》最为著名，影响也最大，是文艺