现代计算代数

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