Computer algebra systems are now ubiquitous in all areas of science and engineering. This highly successful textbook, widely regarded as the 'bible of computer algebra', gives a thorough introduction to the algorithmic basis of the mathematical engine in computer algebra systems. Designed to accompany one- or two-semester courses for advanced undergraduate or graduate students in computer science or mathematics, its comprehensiveness and reliability has also made it 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; and a wide variety of applications (among others, in chemistry, coding theory, cryptography, computational logic, and the design of calendars and musical scales). A great deal of historical information and illustration enlivens the text. In this third edition, errors have been corrected and much of the Fast Euclidean Algorithm chapter has been renovated.
Author(s): Joachim von zur Gathen, Jürgen Gerhard
Edition: 3rd
Publisher: Cambridge University Press
Year: 2013
Language: English
Pages: 812
Tags: Математика;Вычислительная математика;
Modern Computer Algebra......Page 3
Contents......Page 9
Introduction......Page 17
1.2. The RSA cryptosystem......Page 27
1.3. Distributed data structures......Page 34
Part I Euclid......Page 35
2.1. Representation and addition of numbers......Page 45
2.2. Representation and addition of polynomials......Page 48
2.3. Multiplication......Page 50
2.4. Division with remainder......Page 53
Exercises......Page 57
3.1. Euclidean domains......Page 61
3.2. The Extended Euclidean Algorithm......Page 63
3.3. Cost analysis for mathbb Z and F[x]......Page 67
3.4. (Non-)Uniqueness of the gcd......Page 71
Notes......Page 77
Exercises......Page 78
4.1. Modular arithmetic......Page 85
4.2. Modular inverses via Euclid......Page 89
4.3. Repeated squaring......Page 91
4.4. Modular inverses via Fermat......Page 92
4.5. Linear Diophantine equations......Page 93
4.6. Continued fractions and Diophantine approximation......Page 95
4.7. Calendars......Page 99
4.8. Musical scales......Page 100
Notes......Page 104
Exercises......Page 107
5 Modular algorithms and interpolation......Page 113
5.1. Change of representation......Page 116
5.2. Evaluation and interpolation......Page 117
5.3. Application: Secret sharing......Page 119
5.4. The Chinese Remainder Algorithm......Page 120
5.5. Modular determinant computation......Page 125
5.6. Hermite interpolation......Page 129
5.7. Rational function reconstruction......Page 131
5.8. Cauchy interpolation......Page 134
5.9. Padé approximation......Page 137
5.10. Rational number reconstruction......Page 140
5.11. Partial fraction decomposition......Page 144
Notes......Page 147
Exercises......Page 148
6.1. Coefficient growth in the Euclidean Algorithm......Page 157
6.2. Gauß' lemma......Page 163
6.3. The resultant......Page 168
6.4. Modular gcd algorithms......Page 174
6.5. Modular gcd algorithm in F[x,y]......Page 177
6.6. Mignotte's factor bound and a modular gcd algorithm in mathbb Z[x]......Page 180
6.7. Small primes modular gcd algorithms......Page 184
6.8. Application: intersecting plane curves......Page 187
6.9. Nonzero preservation and the gcd of several polynomials......Page 192
6.10. Subresultants......Page 194
6.11. Modular Extended Euclidean Algorithms......Page 199
6.12. Pseudodivision and primitive Euclidean Algorithms......Page 206
6.13. Implementations......Page 209
Notes......Page 213
Exercises......Page 215
7 Application: Decoding BCH codes......Page 225
Exercises......Page 231
Part II Newton......Page 233
8 Fast multiplication......Page 237
8.1. Karatsuba's multiplication algorithm......Page 238
8.2. The Discrete Fourier Transform and the Fast Fourier Transform......Page 243
8.3. Schönhage and Strassen's multiplication algorithm......Page 254
8.4. Multiplication in mathbb Z[x] and R[x,y]......Page 261
Notes......Page 263
Exercises......Page 264
9.1. Division with remainder using Newton iteration......Page 273
9.2. Generalized Taylor expansion and radix conversion......Page 280
9.3. Formal derivatives and Taylor expansion......Page 281
9.4. Solving polynomial equations via Newton iteration......Page 283
9.5. Computing integer roots......Page 287
9.6. Newton iteration, Julia sets, and fractals......Page 289
9.7. Implementations of fast arithmetic......Page 294
Notes......Page 302
Exercises......Page 303
10.1. Fast multipoint evaluation......Page 311
10.2. Fast interpolation......Page 315
10.3. Fast Chinese remaindering......Page 317
Exercises......Page 322
11.1. A fast Euclidean Algorithm for polynomials......Page 329
11.2. Subresultants via Euclid's algorithm......Page 343
Exercises......Page 348
Research problems......Page 349
12.1. Strassen's matrix multiplication......Page 351
12.2. Application: fast modular composition of polynomials......Page 354
12.3. Linearly recurrent sequences......Page 356
12.4. Wiedemann's algorithm and black box linear algebra......Page 362
Notes......Page 368
Exercises......Page 369
Research problem......Page 372
13.1. The Continuous and the Discrete Fourier Transform......Page 375
13.2. Audio and video compression......Page 379
Exercises......Page 384
Part III Gauß......Page 387
14.1. Factorization of polynomials......Page 393
14.2. Distinct-degree factorization......Page 396
14.3. Equal-degree factorization: Cantor and Zassenhaus' algorithm......Page 398
14.4. A complete factoring algorithm......Page 405
14.5. Application: root finding......Page 408
14.6. Squarefree factorization......Page 409
14.7. The iterated Frobenius algorithm......Page 414
14.8. Algorithms based on linear algebra......Page 417
14.9. Testing irreducibility and constructing irreducible polynomials......Page 422
14.10. Cyclotomic polynomials and constructing BCH codes......Page 428
Notes......Page 433
Exercises......Page 438
Research problems......Page 446
15.1. Factoring in mathbb Z[x] and mathbb Q[x]: the basic idea......Page 449
15.2. A factoring algorithm......Page 451
15.3. Frobenius' and Chebotarev's density theorems......Page 457
15.4. Hensel lifting......Page 460
15.5. Multifactor Hensel lifting......Page 466
15.6. Factoring using Hensel lifting: Zassenhaus' algorithm......Page 469
15.7. Implementations......Page 477
Notes......Page 481
Exercises......Page 483
Research problem......Page 487
16.1. Lattices......Page 489
16.2. Lenstra, Lenstra and Lovász' basis reduction algorithm......Page 491
16.3. Cost estimate for basis reduction......Page 496
16.4. From short vectors to factors......Page 503
16.5. A polynomial-time factoring algorithm for mathbb Z[x]......Page 505
16.6. Factoring multivariate polynomials......Page 509
Notes......Page 512
Exercises......Page 514
Research problem......Page 517
17.1. Breaking knapsack-type cryptosystems......Page 519
17.3. Simultaneous Diophantine approximation......Page 521
17.4. Disproof of Mertens' conjecture......Page 524
Exercises......Page 525
Part IV Fermat......Page 527
18.1. Multiplicative order of integers......Page 533
18.2. The Fermat test......Page 535
18.3. The strong pseudoprimality test......Page 536
18.4. Finding primes......Page 539
18.5. The Solovay and Strassen test......Page 545
18.6. Primality tests for special numbers......Page 546
Notes......Page 547
Exercises......Page 550
19.1. Factorization challenges......Page 557
19.2. Trial division......Page 559
19.3. Pollard's and Strassen's method......Page 560
19.4. Pollard's rho method......Page 561
19.5. Dixon's random squares method......Page 565
19.7. Lenstra's elliptic curve method......Page 573
Notes......Page 583
Exercises......Page 585
20.1. Cryptosystems......Page 589
20.2. The RSA cryptosystem......Page 592
20.3. The Diffie–Hellman key exchange protocol......Page 594
20.5. Robin's cryptosystem......Page 595
Exercises......Page 596
Research problems......Page 598
Part V Hilbert......Page 601
21.1. Polynomial ideals......Page 607
21.2. Monomial orders and multivariate division with remainder......Page 611
21.3. Monomial ideals and Hilbert's basis theorem......Page 617
21.4. Gröbner bases and S-polynomials......Page 620
21.5. Buchberger's algorithm......Page 624
21.6. Geometric applications......Page 628
21.7. The complexity of computing Gröbner bases......Page 632
Notes......Page 633
Exercises......Page 635
22.1. Differential algebra......Page 639
22.2. Hermite's method......Page 641
22.3. The method of Lazard, Rioboo, Rothstein, and Trager......Page 643
22.4. Hyperexponential integration: Almkvist & Zeilberger's algorithm......Page 648
Notes......Page 656
Exercises......Page 657
23.1. Polynomial summation......Page 661
23.2. Harmonic numbers......Page 666
23.3. Greatest factorial factorization......Page 669
23.4. Hypergeometric summation: Gosper's algorithm......Page 674
Notes......Page 685
Exercises......Page 687
24.2. Petri nets......Page 693
24.3. Proving identities and analysis of algorithms......Page 697
24.4. Cyclohexane revisited......Page 701
Notes......Page 713
Exercises......Page 714
Appendix......Page 717
25.1. Groups......Page 719
25.2. Rings......Page 721
25.3. Polynomials and fields......Page 724
25.4. Finite fields......Page 727
25.5. Linear algebra......Page 729
25.6. Finite probability spaces......Page 733
25.7. ``Big Oh'' notation......Page 736
25.8. Complexity theory......Page 737
Notes......Page 740
Sources of quotations......Page 741
List of algorithms......Page 746
List of figures and tables......Page 748
References......Page 750
List of notation......Page 784
Index......Page 785
