现代计算代数

　　Modern Computer Algebra Computer algebra systems are gaining more and more importance in all areasof science and engineering. This textbook gives a thorough introduction to thealgorithmic basis of the mathematical engine in computer algebra systems. It is designed to accompany one- or two-semester courses for advanced undergraduate or graduate students in computer science or mathematics. Its comprehensiveness and authority make it also an essential reference for professionals in the area. Special features include： detailed study of algorithms including time analysis; implementation reports on several topics; complete proofs of the mathematical underpinnings; a wide variety of applications （among others， in chemistry， coding theory， cryptography， computational logic， and the design of calendars and musical scales）. Some of this material has never appeared before in book form. Finally， a great deal of historical information and illustration enlivens the text. Joachim yon zur Gathen has a PhD from Universitat Ztirich， taught at University of Toronto from 1981 to 1994， and is now at Universitat Paderbom. Jtirgen Gerhard is completing his PhD and is wissenschaftlicher Mitarbeiter at Universitat Paderborn.

暂缺《现代计算代数》作者简介

Introduction
Cyclohexane,cryptography,codes,andcomputeralgebra
1.1Cyclohexaneconformations
1.2TheRSAcryptosystem
1.3Distributeddatastructures
1.4Computeralgebrasystems
IEuclid
2Fundamentalalgorithms
2.1Representationandadditionofnumbers
2.2Representationandadditionofpolynomials
2.3Multiplication
2.4Divisionwithremainder
Notes
Exercises
3TheEuclideanAlgorithm
3.1Euclideandomains
3.2TheExtendedEuclideanAlgorithm
3.3CostanalysisforZandF[x]
Notes
Exercises
4ApplicationsoftheEuclideanAlgorithm
4.1Modulararithmetic
4.2ModularinversesviaEuclid
4.3Repeatedsquaring
4.4ModularinversesviaFermat
4.5LinearDiophantineequations
4.6ContinuedfractionsandDiophantineapproximation
4.7Calendars
4.8Musicalscales
Notes
Exercises
5Modularalgorithmsandinterpolation
5.1Changeofrepresentation
5.2Evaluationandinterpolation
5.3Application:Secretsharing
5.4TheChineseRemainderAlgorithm
5.5Modulardeterminantcomputation
5.6Hermiteinterpolation
5.7Rationalfunctionreconstruction
5.8Cauchyinterpolation
5.9Padeapproximation
5.10Rationalnumberreconstruction
5.11Partialfractiondecomposition
Notes
Exercises
6Theresultantandgcdcomputation
6.1CoefficientgrowthintheEuclideanAlgorithm
6.2GauB'lemma
6.3Theresultant
6.4Modulargcdalgorithms
6.5ModulargcdalgorithminF[x,y]
6.6Mignotte'sfactorboundandamodulargcdalgorithminZ[x]
6.7Smallprimesmodulargcdalgorithms
6.8Application:intersectingplanecurves
6.9Nonzeropreservationandthegcdofseveralpolynomials
6.10Subresultants
6.11ModularExtendedEuclideanAlgorithms
6.12Pseudo-divisionandprimitiveEuclideanAlgorithms
6.13Implementations
Notes
Exercises
7Application:DecodingBCHcodes
Notes
Exercises
IINewton
Fastmultiplication
8.1Karatsuba'smultiplicationalgorithm
8.2TheDiscreteFourierTransformandtheFastFourierTransform
8.3SchonhageandStrassen'smultiplicationalgorithm
8.4MultiplicationinZ[x]andR[x,y]
Notes
Exercises
9Newtoniteration
9.1DivisionwithremainderusingNewtoniteration
9.2GeneralizedTaylorexpansionandradixconversion
9.3FormalderivativesandTaylorexpansion
9.4SolvingpolynomialequationsviaNewtoniteration
9.5Computingintegerroots
9.6Valuations,Newtoniteration,andJuliasets
9.7Implementationsoffastarithmetic
Notes
Exercises
10Fastpolynomialevaluationandinterpolation
10.1Fastmultipointevaluation
10.2Fastinterpolation
10.3FastChineseremaindering
Notes
Exercises
11FastEuclideanAlgorithm
11.1AfastEuclideanAlgorithmforpolynomials
11.2SubresultantsviaEuclid'salgorithm
Notes
Exercises
12Fastlinearalgebra
12.1Strassen'smatrixmultiplication
12.2Application:fastmodularcompositionofpolynomials
12.3Linearlyrecurrentsequences
12.4Wiedemann'salgorithmandblackboxlinearalgebra
Notes
Exercises
13FourierTransformandimagecompression
13.1TheContinuousandtheDiscreteFourierTransform
13.2Audioandvideocompression
Notes
Exercises
IIIGauB
14Factoringpolynomialsoverfinitefields
14.1Factorizationofpolynomials
14.2Distinct-degreefactorization
14.3Equal-degreefactorization:CantorandZassenhaus'algorithm
14.4Acompletefactoringalgorithm
14.5Application:rootfinding
14.6Squarefreefactorization
14.7TheiteratedFrobeniusalgorithm
14.8Algorithmsbasedonlinearalgebra
14.9Testingirreducibilityandconstructingirreduciblepolynomials
14.10CyclotomicpolynomialsandconstructingBCHcodes
Notes
Exercises
15Henselliftingandfactoringpolynomials
15.1FactoringinZ[x]andQ[x]:thebasicidea
15.2Afactoringalgorithm
15.3Frobenius'andChebotarev'sdensitytheorems
15.4Hensellifting
15.5MultifactorHensellifting
15.6FactoringusingHensellifting:Zassenhaus'algorithm
15.7Implementations
Notes
Exercises
16Shortvectorsinlattices
16.1Lattices
16.2Lenstra,LenstraandLovasz'basisreductionalgorithm
16.3Costestimateforbasisreduction
16.4Fromshortvectorstofactors
16.5Apolynomial-timefactoringalgorithmforQ[x]
16.6Factoringmultivariatepolynomials
Notes
Exercises
17Applicationsofbasisreduction
17.1Breakingknapsack-typecryptosystems
17.2Pseudorandomnumbers
17.3SimultaneousDiophantineapproximation
17.4DisproofofMertens'conjecture
Notes
Exercises
IVFermat
18Primalitytesting
18.1Multiplicativeorderofintegers
18.2TheFermattest
18.3Thestrongpseudoprimalitytest
18.4Findingprimes
18.5TheSolovayandStrassentest
18.6Thecomplexityofprimalitytesting
Notes
Exercises
19Factoringintegers
19.1Factorizationchallenges
19.2Trialdivision
19.3Pollard'sandStrassen'smethod
19.4Pollard'srhomethod
19.5Dixon'srandomsquaresmethod
19.6Pollard'sp-1method
19.7Lenstra'sellipticcurvemethod
Notes
Exercises
20Application:Publickeycryptography
20.1Cryptosystems
20.2TheRSAcryptosystem
20.3TheDiffie-Hellmankeyexchangeprotocol
20.4TheEIGamalcryptosystem
20.5Rabin'scryptosystem
20.6Ellipticcurvesystems
20.7Shortvectorcryptosystems
Notes
Exercises
VHilbert
21Grobnerbases
21.1Polynomialideals
21.2Monomialordersandmultivariatedivisionwithremainder
21.3MonomialidealsandHilbcrt'sbasistheorem
21.4Gr6bnerbasesandS-polynomials
21.5Buchberger'salgorithm
21.6Geometricapplications
21.7ThecomplcxityofcomputingGr6bnerbases
Notes
Exercises
22Symbolicintegration
22.1Differentialalgebra
22.2Hermite'smethod
22.3ThemethodofRothsteinandTrager
Notes
Exercises
23Symbolicsummation
23.1Polynomialsummation
23.2Harmonicnumbers
23.3Greatestfactorialfactorization
23.4Hypergeometricsummation:Gosper'salgorithm
Notes
Exercises
24Applications
24.1Grobnerproofsystems
24.2Petrinets
24.3Provingidentitiesandanalysisofalgorithms
24.4Cyclohexanerevisited
Notes
Exercises
Appendix
25Fundamentalconcepts
25.1Groups
25.2Rings
25.3Polynomialsandfields
25.4Finitefields
25.5Linearalgebra
25.6Finiteprobabilityspaces
25.7"BigOh"notation
25.8Complexitytheory
Notes
Sourcesofillustrations
Sourcesofquotations
Listofalgorithms
Listoffiguresandtables
References
Listofnotation
Index