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

Also Available On

Categories

Arts & Photography489Biographies & Memoirs82Business & Money147Children's Books1715Christian Books & Bibles991Comics & Graphic Novels6Computers & Technology877Cookbooks, Food & Wine24Crafts, Hobbies & Home207Education & Teaching3899Engineering & Transportation1Gay & Lesbian3Health, Fitness & Dieting14History5882Humor & Entertainment165Law154Literature & Fiction19916Medical Books2Mystery, Thriller & Suspense24Other3126Parenting & Relationships12Politics & Social Sciences1478Professional & Technical26Reference11Religion & Spirituality1749Romance273Science & Math1240Science Fiction & Fantasy210Self-Help42Sports & Outdoors48Teen & Young Adult161Test Preparation175Travel115

Curated Lists

#### Free Machine Learning Books

11 Books

- Pattern Recognition and Machine Learning (Information Science and Statistics)
- by Christopher M. Bishop
- Data mining
- by I. H. Witten
- The Elements of Statistical Learning: Data Mining, Inference, and Prediction
- by Various

#### Free Chemistry Textbooks

8 Books

- CK-12 Chemistry
- by Various
- Chemistry Grade 10 [CAPS]
- by Free High School Science Texts Project
- General Chemistry II
- by John Hutchinson

#### Free Mathematics Textbooks

21 Books

- Microsoft Word - How to Use Advanced Algebra II.doc
- by Jonathan Emmons
- Advanced Algebra II: Activities and Homework
- by Kenny Felder
- de2de
- by

#### Free Children Books

38 Books

- The Sun Who Lost His Way
- by
- Tania is a Detective
- by Kanika G
- Firenze_s-Light
- by

#### Free Java Books

10 Books

- Java 3D Programming
- by Daniel Selman
- The Java EE 6 Tutorial
- by Oracle Corporation
- JavaKid811
- by

- Jamaica Primary Social Studies 2nd Edition Student's Book 4
- by Eulie Mantock, Trineta Fendall, Clare Eastland
- Reggae Readers Student's Book 1
- by Louis Fidge
- Reggae Readers Student's Book 2
- by Louis Fidge