Skip to content

Computational Introduction to Number Theory and Algebra

Spend $50 to get a free DVD!

ISBN-10: 0521516447

ISBN-13: 9780521516440

Edition: 2nd 2008

Authors: Victor Shoup

List price: $49.99
Blue ribbon 30 day, 100% satisfaction guarantee!
Out of stock
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

Description:

Number theory and algebra play an increasingly significant role in computing and communications, as evidenced by the striking applications of these subjects to such fields as cryptography and coding theory. This introductory book emphasizes algorithms and applications, such as cryptography and error correcting codes, and is accessible to a broad audience. The presentation alternates between theory and applications in order to motivate and illustrate the mathematics. The mathematical coverage includes the basics of number theory, abstract algebra and discrete probability theory. This edition now includes over 150 new exercises, ranging from the routine to the challenging, that flesh out the…    
Customers also bought

Book details

List price: $49.99
Edition: 2nd
Copyright year: 2008
Publisher: University of Cambridge ESOL Examinations
Publication date: 12/4/2008
Binding: Hardcover
Pages: 600
Size: 7.00" wide x 9.75" long x 1.25" tall
Weight: 2.684
Language: English

Victor Shoup is a Professor in the Department of Computer Science at the Courant Institute of Mathematical Sciences, New York University.

Preface
Preliminaries
Basic properties of the integers
Divisibility and primality
Ideals and greatest common divisors
Some consequences of unique factorization
Congruences
Equivalence relations
Definitions and basic properties of congruences
Solving linear congruences
The Chinese remainder theorem
Residue classes
Euler's phi function
Euler's theorem and Fermat's little theorem
Quadratic residues
Summations over divisors
Computing with large integers
Asymptotic notation
Machine models and complexity theory
Basic integer arithmetic
Computing in Z<sub>n</sub>
Faster integer arithmetic (*)
Notes
Euclid's algorithm
The basic Euclidean algorithm
The extended Euclidean algorithm
Computing modular inverses and Chinese remaindering
Speeding up algorithms via modular computation
An effective version of Fermat's two squares theorem
Rational reconstruction and applications
The RSA cryptosystem
Notes
The distribution of primes
Chebyshev's theorem on the density of primes
Bertrand's postulate
Mertens' theorem
The sieve of Eratosthenes
The prime number theorem ...and beyond
Notes
Abelian groups
Definitions, basic properties, and examples
Subgroups
Cosets and quotient groups
Group homomorphisms and isomorphisms
Cyclic groups
The structure of finite abelian groups (*)
Rings
Definitions, basic properties, and examples
Polynomial rings
Ideals and quotient rings
Ring homomorphisms and isomorphisms
The structure of Z<sup>*</sup><sub>n</sub>
Finite and discrete probability distributions
Basic definitions
Conditional probability and independence
Random variables
Expectation and variance
Some useful bounds
Balls and bins
Hash functions
Statistical distance
Measures of randomness and the leftover hash lemma (*)
Discrete probability distributions
Notes
Probabilistic algorithms
Basic definitions
Generating a random number from a given interval
The generate and test paradigm
Generating a random prime
Generating a random non-increasing sequence
Generating a random factored number
Some complexity theory
Notes
Probabilistic primality testing
Trial division
The Miller-Rabin test
Generating random primes using the Miller-Rabin test
Factoring and computing Euler's phi function
Notes
Finding generators and discrete logarithms in Z<sup>*</sup><sub>p</sub>
Finding a generator for Z<sup>*</sup><sub>p</sub>
Computing discrete logarithms in Z<sup>*</sup><sub>p</sub>
The Diffie-Hellman key establishment protocol
Notes
Quadratic reciprocity and computing modular square roots
The Legendre symbol
The Jacobi symbol
Computing the Jacobi symbol
Testing quadratic residuosity
Computing modular square roots
The quadratic residuosity assumption
Notes
Modules and vector spaces
Definitions, basic properties, and examples
Submodules and quotient modules
Module homomorphisms and isomorphisms
Linear independence and bases
Vector spaces and dimension
Matrices
Basic definitions and properties
Matrices and linear maps
The inverse of a matrix
Gaussian elimination
Applications of Gaussian elimination
Notes
Subexponential-time discrete logarithms and factoring
Smooth numbers
An algorithm for discrete logarithms
An algorithm for factoring integers
Practical improvements
Notes
More rings
Algebras
The field of fractions of an integral domain
Unique factorization of polynomials
Polynomial congruences
Minimal polynomials
General properties of extension fields
Formal derivatives
Formal power series and Laurent series
Unique factorization domains (*)
Notes
Polynomial arithmetic and applications
Basic arithmetic
Computing minimal polynomials in F[x]/(f)(I)
Euclid's algorithm
Computing modular inverses and Chinese remaindering
Rational function reconstruction and applications
Faster polynomial arithmetic (*)
Notes
Linearly generated sequences and applications
Basic definitions and properties
Computing minimal polynomials: a special case
Computing minimal polynomials: a more general case
Solving sparse linear systems
Computing minimal polynomials in F[X]/(f)(II)
The algebra of linear transformations (*)
Notes
Finite fields
Preliminaries
The existence of finite fields
The subfield structure and uniqueness of finite fields
Conjugates, norms and traces
Algorithms for finite fields
Tests for and constructing inrreducible polynomials
Computing minimal polynomials in F[X](f)(III)
Factoring polynomials: square-free decomposition
Factoring polynomials: the Cantor-Zassenhaus algorithm
Factoring polynomials: Berlekamp's algorithm
Deterministic factorization algorithms (*)
Notes
Deterministic primality testing
The basic idea
The algorithm and its analysis
Notes
Appendix: Some useful facts
Bibliography
Index of notation
Index