Readings in Number Theory and Computing
Inspired
by this
page by @cmeik I've
decided to create my own list of readings about Mathematics,
specifically about Number Theory and Computing.
What I've found interesting about Number Theory is that
since it mostly deals with Integer Numbers, its consequences
are quite easy to "see". Besides, Number Theory is
widely used for Cryptography, Random Number Generators and
more, so it's quite interesting to at least have an idea of
what it is about.
Books
Some of the books are purely theoretical, but most of them
have direct applications in computing. I don't claim to have
read all these books, but I have read several chapters or
sections on each of them.
- An Introduction to the Theory of Numbers
- Hardy, G. H., and Edward Maitland Wright. 2008 (First
ed. 1938). This is basically THE book on Number Theory. The
style is very dry, it was written back in 1938 but it will
guide you through almost every theorem in Number
Theory. This is a mostly theoretical book.
- Applied algebra for the computer sciences
- Gill, Arthur. 1976. This is an old book, but quite
juicy. It touches a lot of topics, like boolean algebra,
sets, groups, rings and fields, error correcting codes and
even graph theory. Today you can find it mostly second hand, so it's
rather cheap.
- A Computational Introduction to Number Theory and Algebra
- Shoup, Victor. 2008. I'm really happy with this
book. The explanations for the various topics are quite
clear and easy to follow. You also learn about the actual
applications of these theories. Also
the computational part on the title already tells
us that there are lot of algorithms in this book. The
complexity of the running time of the algorithms is analyzed
as well.
- Prime numbers: a computational perspective
- Crandall, Richard E., and Carl Pomerance. 2005. This is
a very well presented book on the practicalities of Prime
Numbers, mostly with their application to cryptography. One
of the authors was the chief cryptographer at Apple, while
the other author has many theorems under his name.
- Groups and symmetry
- Armstrong, M. A. 1988. This book presents Group Theory
and Symmetry for an undergraduate level, so it's quite easy
to follow and a nice intro for the other, more advanced
books. Lots of pictures an examples as well.
- Permutation groups
- Dixon, John D., and Brian Mortimer. 1996. A more
advanced introduction to Permutation Groups.
- Handbook of computational group theory
- Holt, Derek F., Bettina Eick, and Eamonn
A. O'Brien. 2005. This book is really great. Its first
chapter lays out the basics about group theory in a very
nice and easy to follow manner. This is quite nice, since
once you start going to the more advanced chapters you
actually know what the authors are talking about. Each
chapter ends with a section on the applications of what you
have just read, so that's a nice thing to have.
- A course in number theory and cryptography
- Koblitz, Neal. 1987. This books explains most of the early cryptography and computing techniques and has an intro to elliptic curves.
- The design of Rijndael: AES -- the Advanced Encryption Standard
- Daemen, Joan, and Vincent Rijmen. 2002. This book is a
must have. It explains the design of AES and it really shows
how some areas of mathematics that look quite abstract and not so useful
can be applied to design an algorithm like this
one.
- Concrete mathematics: a foundation for computer science
- Graham, Ronald L., Donald Ervin Knuth, and Oren
Patashnik. 1989. This book is a very good companion to
TAOCP, giving a more detailed intro to the mathematics used
in TAOCP
- Hacker's
Delight
- Warren, Henry S. 2012. The interesting thing about this
book is that it touches a lot of topics that are related to
numbers and computing and how they are actually implemented
in a computer, with limited RAM, limited word sizes and so
on. The Number Theory of the previous books is nice, but
this book shows how the actual CPU architecture plays a very
important role in this kind of numeric algorithms.
- The Art of Computer Programming. Volume 2, Seminumerical algorithms
- Knuth, Donald Ervin. 1998. This massive volume by Knuth
explains many of the algorithms related with numbers as the
title shows. From how random number generators work, to
working with different radixes, up to all kinds of
algorithms related to polynomials.
Papers
I haven't read that many papers on the topic, since I have
focused mostly on learning from books. Nonetheless here are a
couple of interesting papers on Group Theory
- The mathematics of perfect shuffles
- Diaconis, Persi, R. L. Graham, and W. M. Kantor. 1982.
- Efficient Representation of Perm Groups
- Knuth, Donald E. 1991.
Online Resources
Some websites/online resources that I have used to learn
about maths.
- Project Euler
- "Project Euler is a series of challenging
mathematical/computer programming problems that will require
more than just mathematical insights to solve"
- Math and Programming
- by Jeremy Kun with really good examples and explanations of various topics.
- Mathematics Stack Exchange
- Questions and Answers about maths.
- @algebrafact
- Curated by @JohnDCook