This textbook offers an algorithmic introduction to the field of computer algebra. A leading expert in the field, the author guides readers through numerous hands-on tutorials designed to build practical skills and algorithmic thinking. This implementation-oriented approach equips readers with versatile tools that can be used to enhance studies in mathematical theory, applications, or teaching. Presented using Mathematica code, the book is fully supported by downloadable sessions in Mathematica, Maple, and Maxima.
Opening with an introduction to computer algebra systems and the basics of programming mathematical algorithms, the book goes on to explore integer arithmetic. A chapter on modular arithmetic completes the number-theoretic foundations, which are then applied to coding theory and cryptography. From here, the focus shifts to polynomial arithmetic and algebraic numbers, with modern algorithms allowing the efficient factorization of polynomials. The final chapters offer extensions into more advanced topics: simplification and normal forms, power series, summation formulas, and integration.
Computer Algebra is an indispensable resource for mathematics and computer science students new to the field. Numerous examples illustrate algorithms and their implementation throughout, with online support materials to encourage hands-on exploration. Prerequisites are minimal, with only a knowledge of calculus and linear algebra assumed. In addition to classroom use, the elementary approach and detailed index make this book an ideal reference for algorithms in computer algebra.
Author(s): Wolfram Koepf
Series: Springer Undergraduate Texts in Mathematics and Technology
Publisher: Springer
Year: 2021
Language: English
Pages: 384
City: Cham
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
