A Computational Introduction to Number Theory and Algebra (Version 2)
Free

A Computational Introduction to Number Theory and Algebra (Version 2)

By Victor Shoup
Free
Book Description
Table of Contents
  • Title
  • Contents
  • Preface
  • Preliminaries
  • 1 Basic properties of the integers
    • 1.1 Divisibility and primality
    • 1.2 Ideals and greatest common divisors
    • 1.3 Some consequences of unique factorization
  • 2 Congruences
    • 2.1 Equivalence relations
    • 2.2 Definitions and basic properties of congruences
    • 2.3 Solving linear congruences
    • 2.4 The Chinese remainder theorem
    • 2.5 Residue classes
    • 2.6 Euler's phi function
    • 2.7 Euler's theorem and Fermat's little theorem
    • 2.8 Quadratic residues
    • 2.9 Summations over divisors
  • 3 Computing with large integers
    • 3.1 Asymptotic notation
    • 3.2 Machine models and complexity theory
    • 3.3 Basic integer arithmetic
    • 3.4 Computing in Zn
    • 3.5 Faster integer arithmetic (*)
    • 3.6 Notes
  • 4 Euclid's algorithm
    • 4.1 The basic Euclidean algorithm
    • 4.2 The extended Euclidean algorithm
    • 4.3 Computing modular inverses and Chinese remaindering
    • 4.4 Speeding up algorithms via modular computation
    • 4.5 An effective version of Fermat's two squares theorem
    • 4.6 Rational reconstruction and applications
    • 4.7 The RSA cryptosystem
    • 4.8 Notes
  • 5 The distribution of primes
    • 5.1 Chebyshev's theorem on the density of primes
    • 5.2 Bertrand's postulate
    • 5.3 Mertens' theorem
    • 5.4 The sieve of Eratosthenes
    • 5.5 The prime number theorem …and beyond
    • 5.6 Notes
  • 6 Abelian groups
    • 6.1 Definitions, basic properties, and examples
    • 6.2 Subgroups
    • 6.3 Cosets and quotient groups
    • 6.4 Group homomorphisms and isomorphisms
    • 6.5 Cyclic groups
    • 6.6 The structure of finite abelian groups (*)
  • 7 Rings
    • 7.1 Definitions, basic properties, and examples
    • 7.2 Polynomial rings
    • 7.3 Ideals and quotient rings
    • 7.4 Ring homomorphisms and isomorphisms
    • 7.5 The structure of Zn*
  • 8 Finite and discrete probability distributions
    • 8.1 Basic definitions
    • 8.2 Conditional probability and independence
    • 8.3 Random variables
    • 8.4 Expectation and variance
    • 8.5 Some useful bounds
    • 8.6 Balls and bins
    • 8.7 Hash functions
    • 8.8 Statistical distance
    • 8.9 Measures of randomness and the leftover hash lemma (*)
    • 8.10 Discrete probability distributions
    • 8.11 Notes
  • 9 Probabilistic algorithms
    • 9.1 Basic definitions
    • 9.2 Generating a random number from a given interval
    • 9.3 The generate and test paradigm
    • 9.4 Generating a random prime
    • 9.5 Generating a random non-increasing sequence
    • 9.6 Generating a random factored number
    • 9.7 Some complexity theory
    • 9.8 Notes
  • 10 Probabilistic primality testing
    • 10.1 Trial division
    • 10.2 The Miller--Rabin test
    • 10.3 Generating random primes using the Miller--Rabin test
    • 10.4 Factoring and computing Euler's phi function
    • 10.5 Notes
  • 11 Finding generators and discrete logarithms in Zp*
    • 11.1 Finding a generator for Zp*
    • 11.2 Computing discrete logarithms in Zp*
    • 11.3 The Diffie--Hellman key establishment protocol
    • 11.4 Notes
  • 12 Quadratic reciprocity and computing modular square roots
    • 12.1 The Legendre symbol
    • 12.2 The Jacobi symbol
    • 12.3 Computing the Jacobi symbol
    • 12.4 Testing quadratic residuosity
    • 12.5 Computing modular square roots
    • 12.6 The quadratic residuosity assumption
    • 12.7 Notes
  • 13 Modules and vector spaces
    • 13.1 Definitions, basic properties, and examples
    • 13.2 Submodules and quotient modules
    • 13.3 Module homomorphisms and isomorphisms
    • 13.4 Linear independence and bases
    • 13.5 Vector spaces and dimension
  • 14 Matrices
    • 14.1 Basic definitions and properties
    • 14.2 Matrices and linear maps
    • 14.3 The inverse of a matrix
    • 14.4 Gaussian elimination
    • 14.5 Applications of Gaussian elimination
    • 14.6 Notes
  • 15 Subexponential-time discrete logarithms and factoring
    • 15.1 Smooth numbers
    • 15.2 An algorithm for discrete logarithms
    • 15.3 An algorithm for factoring integers
    • 15.4 Practical improvements
    • 15.5 Notes
  • 16 More rings
    • 16.1 Algebras
    • 16.2 The field of fractions of an integral domain
    • 16.3 Unique factorization of polynomials
    • 16.4 Polynomial congruences
    • 16.5 Minimal polynomials
    • 16.6 General properties of extension fields
    • 16.7 Formal derivatives
    • 16.8 Formal power series and Laurent series
    • 16.9 Unique factorization domains (*)
    • 16.10 Notes
  • 17 Polynomial arithmetic and applications
    • 17.1 Basic arithmetic
    • 17.2 Computing minimal polynomials in F[X]/(f) (I)
    • 17.3 Euclid's algorithm
    • 17.4 Computing modular inverses and Chinese remaindering
    • 17.5 Rational function reconstruction and applications
    • 17.6 Faster polynomial arithmetic (*)
    • 17.7 Notes
  • 18 Linearly generated sequences and applications
    • 18.1 Basic definitions and properties
    • 18.2 Computing minimal polynomials: a special case
    • 18.3 Computing minimal polynomials: a more general case
    • 18.4 Solving sparse linear systems
    • 18.5 Computing minimal polynomials in F[X]/(f) (II)
    • 18.6 The algebra of linear transformations (*)
    • 18.7 Notes
  • 19 Finite fields
    • 19.1 Preliminaries
    • 19.2 The existence of finite fields
    • 19.3 The subfield structure and uniqueness of finite fields
    • 19.4 Conjugates, norms and traces
  • 20 Algorithms for finite fields
    • 20.1 Tests for and constructing irreducible polynomials
    • 20.2 Computing minimal polynomials in F[X]/(f) (III)
    • 20.3 Factoring polynomials: square-free decomposition
    • 20.4 Factoring polynomials: the Cantor--Zassenhaus algorithm
    • 20.5 Factoring polynomials: Berlekamp's algorithm
    • 20.6 Deterministic factorization algorithms (*)
    • 20.7 Notes
  • 21 Deterministic primality testing
    • 21.1 The basic idea
    • 21.2 The algorithm and its analysis
    • 21.3 Notes
  • Appendix: Some useful facts
  • Bibliography
  • Index of notation
  • Index
The book hasn't received reviews yet.
You May Also Like
Mathematics Grade 8
Free
Mathematics Grade 8
By Siyavula Uploader
Mathematics Grade 9
Free
Mathematics Grade 9
By Siyavula Uploader
Calculus
Free
Calculus
By Unknown
aata-20150812
Free
aata-20150812
By Unknown
Mathematics Grade 4
Free
Mathematics Grade 4
By Siyavula Uploader
Algebra
Free
Algebra
By Jason Haap
Applied Probability
Free
Applied Probability
By Paul Pfeiffer
Mathematics Grade 3
Free
Mathematics Grade 3
By Siyavula Uploader
Also Available On
Categories
Curated Lists