You are previewing Modern Computer Algebra, Third Edition.
O'Reilly logo
Modern Computer Algebra, Third Edition

Book Description

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.

Table of Contents

  1. Cover
  2. Half Title
  3. Title
  4. Copyrights
  5. Dedication
  6. Contents
  7. Introduction
  8. 1 Cyclohexane, cryptography, codes, and computer algebra
    1. 1.1 Cyclohexane conformations
    2. 1.2 The RSA cryptosystem
    3. 1.3 Distributed data structures
    4. 1.4 Computer algebra systems
  9. I Euclid
    1. 2 Fundamental algorithms
      1. 2.1 Representation and addition of numbers
      2. 2.2 Representation and addition of polynomials
      3. 2.3 Multiplication
      4. 2.4 Division with remainder
      5. Notes
      6. Exercises
    2. 3 The Euclidean Algorithm
      1. 3.1 Euclidean domains
      2. 3.2 The Extended Euclidean Algorithm
      3. 3.3 Cost analysis for Z and F[x]
      4. 3.4 (Non-)Uniqueness of the gcd
      5. Notes
      6. Exercises
    3. 4 Applications of the Euclidean Algorithm
      1. 4.1 Modular arithmetic
      2. 4.2 Modular inverses via Euclid
      3. 4.3 Repeated squaring
      4. 4.4 Modular inverses via Fermat
      5. 4.5 Linear Diophantine equations
      6. 4.6 Continued fractions and Diophantine approximation
      7. 4.7 Calendars
      8. 4.8 Musical scales
      9. Notes
      10. Exercises
    4. 5 Modular algorithms and interpolation
      1. 5.1 Change of representation
      2. 5.2 Evaluation and interpolation
      3. 5.3 Application: Secret sharing
      4. 5.4 The Chinese Remainder Algorithm
      5. 5.5 Modular determinant computation
      6. 5.6 Hermite interpolation
      7. 5.7 Rational function reconstruction
      8. 5.8 Cauchy interpolation
      9. 5.9 Padé approximation
      10. 5.10 Rational number reconstruction
      11. 5.11 Partial fraction decomposition
      12. Notes
      13. Exercises
    5. 6 The resultant and gcd computation
      1. 6.1 Coefficient growth in the Euclidean Algorithm
      2. 6.2 Gauß’ lemma
      3. 6.3 The resultant
      4. 6.4 Modular gcd algorithms
      5. 6.5 Modular gcd algorithm in F [x, y]
      6. 6.6 Mignotte’s factor bound and a modular gcd algorithm in Z[x]
      7. 6.7 Small primes modular gcd algorithms
      8. 6.8 Application: intersecting plane curves
      9. 6.9 Nonzero preservation and the gcd of several polynomials
      10. 6.10 Subresultants
      11. 6.11 Modular Extended Euclidean Algorithms
      12. 6.12 Pseudodivision and primitive Euclidean Algorithms
      13. 6.13 Implementations
      14. Notes
      15. Exercises
    6. 7 Application: Decoding BCH codes
      1. Notes
      2. Exercises
  10. II Newton
    1. 8 Fast multiplication
      1. 8.1 Karatsuba’s multiplication algorithm
      2. 8.2 The Discrete Fourier Transform and the Fast Fourier Transform
      3. 8.3 Schönhage and Strassen’s multiplication algorithm
      4. 8.4 Multiplication in Z[x] and R[x, y]
      5. Notes
      6. Exercises
    2. 9 Newton iteration
      1. 9.1 Division with remainder using Newton iteration
      2. 9.2 Generalized Taylor expansion and radix conversion
      3. 9.3 Formal derivatives and Taylor expansion
      4. 9.4 Solving polynomial equations via Newton iteration
      5. 9.5 Computing integer roots
      6. 9.6 Newton iteration, Julia sets, and fractals
      7. 9.7 Implementations of fast arithmetic
      8. Notes
      9. Exercises
    3. 10 Fast polynomial evaluation and interpolation
      1. 10.1 Fast multipoint evaluation
      2. 10.2 Fast interpolation
      3. 10.3 Fast Chinese remaindering
      4. Notes
      5. Exercises
    4. 11 Fast Euclidean Algorithm
      1. 11.1 A fast Euclidean Algorithm for polynomials
      2. 11.2 Subresultants via Euclid’s algorithm
      3. Notes
      4. Exercises
    5. 12 Fast linear algebra
      1. 12.1 Strassen’s matrix multiplication
      2. 12.2 Application: fast modular composition of polynomials
      3. 12.3 Linearly recurrent sequences
      4. 12.4 Wiedemann’s algorithm and black box linear algebra
      5. Notes
      6. Exercises
    6. 13 Fourier Transform and image compression
      1. 13.1 The Continuous and the Discrete Fourier Transform
      2. 13.2 Audio and video compression
      3. Notes
      4. Exercises
  11. III Gauß
    1. 14 Factoring polynomials over finite fields
      1. 14.1 Factorization of polynomials
      2. 14.2 Distinct-degree factorization
      3. 14.3 Equal-degree factorization: Cantor and Zassenhaus’ algorithm
      4. 14.4 A complete factoring algorithm
      5. 14.5 Application: root finding
      6. 14.6 Squarefree factorization
      7. 14.7 The iterated Frobenius algorithm
      8. 14.8 Algorithms based on linear algebra
      9. 14.9 Testing irreducibility and constructing irreducible polynomials
      10. 14.10 Cyclotomic polynomials and constructing BCH codes
      11. Notes
      12. Exercises
    2. 15 Hensel lifting and factoring polynomials
      1. 15.1 Factoring in Z[x] and Q[x]: the basic idea
      2. 15.2 A factoring algorithm
      3. 15.3 Frobenius’ and Chebotarev’s density theorems
      4. 15.4 Hensel lifting
      5. 15.5 Multifactor Hensel lifting
      6. 15.6 Factoring using Hensel lifting: Zassenhaus’ algorithm
      7. 15.7 Implementations
      8. Notes
      9. Exercises
    3. 16 Short vectors in lattices
      1. 16.1 Lattices
      2. 16.2 Lenstra, Lenstra and Lovás’ basis reduction algorithm
      3. 16.3 Cost estimate for basis reduction
      4. 16.4 From short vectors to factors
      5. 16.5 A polynomial-time factoring algorithm for Z[x]
      6. 16.6 Factoring multivariate polynomials
      7. Notes
      8. Exercises
    4. 17 Applications of basis reduction
      1. 17.1 Breaking knapsack-type cryptosystems
      2. 17.2 Pseudorandom numbers
      3. 17.3 Simultaneous Diophantine approximation
      4. 17.4 Disproof of Mertens’ conjecture
      5. Notes
      6. Exercises
  12. IV Fermat
    1. 18 Primality testing
      1. 18.1 Multiplicative order of integers
      2. 18.2 The Fermat test
      3. 18.3 The strong pseudoprimality test
      4. 18.4 Finding primes
      5. 18.5 The Solovay and Strassen test
      6. 18.6 Primality tests for special numbers
      7. Notes
      8. Exercises
    2. 19 Factoring integers
      1. 19.1 Factorization challenges
      2. 19.2 Trial division
      3. 19.3 Pollard’s and Strassen’s method
      4. 19.4 Pollard’s rho method
      5. 19.5 Dixon’s random squares method
      6. 19.6 Pollard’s p - 1 method
      7. 19.7 Lenstra’s elliptic curve method
      8. Notes
      9. Exercises
    3. 20 Application: Public key cryptography
      1. 20.1 Cryptosystems
      2. 20.2 The RSA cryptosystem
      3. 20.3 The Diffie–Hellman key exchange protocol
      4. 20.4 The ElGamal cryptosystem
      5. 20.5 Rabin’s cryptosystem
      6. 20.6 Elliptic curve systems
      7. Notes
      8. Exercises
  13. V Hilbert
    1. 21 Gröbner bases
      1. 21.1 Polynomial ideals
      2. 21.2 Monomial orders and multivariate division with remainder
      3. 21.3 Monomial ideals and Hilbert’s basis theorem
      4. 21.4 Gröbner bases and S-polynomials
      5. 21.5 Buchberger’s algorithm
      6. 21.6 Geometric applications
      7. 21.7 The complexity of computing Gröbner bases
      8. Notes
      9. Exercises
    2. 22 Symbolic integration
      1. 22.1 Differential algebra
      2. 22.2 Hermite’s method
      3. 22.3 The method of Lazard, Rioboo, Rothstein, and Trager
      4. 22.4 Hyperexponential integration: Almkvist & Zeilberger’s algorithm
      5. Notes
      6. Exercises
    3. 23 Symbolic summation
      1. 23.1 Polynomial summation
      2. 23.2 Harmonic numbers
      3. 23.3 Greatest factorial factorization
      4. 23.4 Hypergeometric summation: Gosper’s algorithm
      5. Notes
      6. Exercises
    4. 24 Applications
      1. 24.1 Gröbner proof systems
      2. 24.2 Petri nets
      3. 24.3 Proving identities and analysis of algorithms
      4. 24.4 Cyclohexane revisited
      5. Notes
      6. Exercises
    5. Appendix
    6. 25 Fundamental concepts
      1. 25.1 Groups
      2. 25.2 Rings
      3. 25.3 Polynomials and fields
      4. 25.4 Finite fields
      5. 25.5 Linear algebra
      6. 25.6 Finite probability spaces
      7. 25.7 "Big Oh" notation
      8. 25.8 Complexity theory
      9. Notes
  14. Sources of illustrations
  15. Sources of quotations
  16. List of algorithms
  17. List of figures and tables
  18. References
  19. List of notation
  20. Index