Computer Algebra: An Algorithm-Oriented Introduction

Preface
Contents
Chapter 1 Introduction to Computer Algebra
	1.1 Capabilities of Computer Algebra Systems
	1.2 Additional Remarks
	1.3 Exercises
Chapter 2 Programming in Computer Algebra Systems
	2.1 Internal Representation of Expressions
	2.2 Pattern Matching
	2.3 Control Structures
	2.4 Recursion and Iteration
	2.5 Remember Programming
	2.6 Divide-and-Conquer Programming
	2.7 Programming through Pattern Matching
	2.8 Additional Remarks
	2.9 Exercises
Chapter 3 Number Systems and Integer Arithmetic
	3.1 Number Systems
	3.2 Integer Arithmetic: Addition and Multiplication
	3.3 Integer Arithmetic: Division with Remainder
	3.4 The Extended Euclidean Algorithm
	3.5 Unique Factorization
	3.6 Rational Arithmetic
	3.7 Additional Remarks
	3.8 Exercises
Chapter 4 Modular Arithmetic
	4.1 Residue Class Rings
	4.2 Modulare Square Roots
	4.3 Chinese Remainder Theorem
	4.4 Fermat’s Little Theorem
	4.5 Modular Logarithms
	4.6 Pseudoprimes
	4.7 Additional Remarks
	4.8 Exercises
Chapter 5 Coding Theory and Cryptography
	5.1 Basic Concepts of Coding Theory
	5.2 Prefix Codes
	5.3 Check Digit Systems
	5.4 Error Correcting Codes
	5.5 Asymmetric Ciphers
	5.6 Additional Remarks
	5.7 Exercises
Chapter 6 Polynomial Arithmetic
	6.1 Polynomial Rings
	6.2 Multiplication: The Karatsuba Algorithm
	6.3 Fast Multiplication with FFT
	6.4 Division with Remainder
	6.5 Polynomial Interpolation
	6.6 The Extended Euclidean Algorithm
	6.7 Unique Factorization
	6.8 Squarefree Factorization
	6.9 Rational Functions
	6.10 Additional Remarks
	6.11 Exercises
Chapter 7 Algebraic Numbers
	7.1 Polynomial Quotient Rings
	7.2 Chinese Remainder Theorem
	7.3 Algebraic Numbers
	7.4 Finite Fields
	7.5 Resultants
	7.6 Polynomial Systems of Equations
	7.7 Additional Remarks
	7.8 Exercises
Chapter 8 Factorization in Polynomial Rings
	8.1 Preliminary Considerations
	8.2 Efficient Factorization in Zp[x]
	8.3 Squarefree Factorization of Polynomials over Finite Fields
	8.4 Efficient Factorization in Q[x]
	8.5 Hensel Lifting
	8.6 Multivariate Factorization
	8.7 Additional Remarks
	8.8 Exercises
Chapter 9 Simplification and Normal Forms
	9.1 Normal Forms and Canonical Forms
	9.2 Normal Forms and Canonical Forms for Polynomials
	9.3 Normal Forms for Rational Functions
	9.4 Normal Forms for Trigonometric Polynomials
	9.5 Additional Remarks
	9.6 Exercises
Chapter 10 Power Series
	10.1 Formal Power Series
	10.2 Taylor Polynomials
	10.3 Computation of Formal Power Series
		10.3.1 Holonomic Differential Equations
		10.3.2 Holonomic Recurrence Equations
		10.3.3 Hypergeometric Functions
		10.3.4 Efficient Computation of Taylor Polynomials of Holonomic Functions
	10.4 Algebraic Functions
	10.5 Implicit Functions
	10.6 Additional Remarks
	10.7 Exercises
Chapter 11 Algorithmic Summation
	11.1 Definite Summation
	11.2 Difference Calculus
	11.3 Indefinite Summation
	11.4 Indefinite Summation of Hypergeometric Terms
	11.5 Definite Summation of Hypergeometric Terms
	11.6 Additional Remarks
	11.7 Exercises
Chapter 12 Algorithmic Integration
	12.1 The Bernoulli Algorithm for Rational Functions
	12.2 Algebraic Prerequisites
	12.3 Rational Part
	12.4 Logarithmic Case
	12.5 Additional Remarks
	12.6 Exercises
References
List of Symbols
Mathematica List of Keywords
Index