# Abstract algebra for Theoretical Computer Scientists

I have a reasonable undergrad math education but have never been 100% comfortable with abstract algebra (the mathematics of groups, rings, fields etc. ). I think this was partly as I needed to see applications and any that I could find were in physics, not CS. As my interest is really CS, are there any materials available now (online drafts, lecture notes, videos, books) that cover abstract algebra from the point of view of applications in CS and in particularly algorithms/theory? I am happy for these applications to be entirely theoretical but they shouldn't assume any pre-existing abstract algebra knowledge.

I am pretty sure that were these resources to exist, they would be appreciated by a large number of CS researchers.

• stackexchange gives plenty of "Related" questions to yours on the right hand side bar. Please read them first, in particular Algebraic structures in Computer Science. – Uday Reddy Feb 24 '13 at 10:57
• @UdayReddy Thanks. I am reading those and some of the links have good stuff in them. However, ideally I am looking for a lecture course entitled "An introduction to abstract algebra for theoretical computer scientists" (as a random fictional example) rather than a list of CS results where abstract algebra have been crucial. My interest is really on algorithms/theory and far from category theory, for example. – Majid Feb 24 '13 at 11:11

You could try the notes from Madhu Sudan's course: Algebra and Computation

• This answers the question very nicely. It's a shame that "Mathematics for Computer Science" courses such as MIT's 6.042 don't seem to cover any abstract algebra. At least not the ones I have seen. – Majid Feb 25 '13 at 12:51

One possibily path into abstract algebra could be to look at it from point of view of cryptography, which is about algorithms on finite field. Fields are rings, and fields are also two groups coupled by simple laws. Field theory uses vector spaces in prominent position (Galois theory), so this angle should cover a lot of abstract algebra. The book

could therefore be of interest.

My personal recommendation would be to ignore applications, and study a basic undergraduate maths text on abstract algebra. There is no shortage of those. Just trust that all this stuff is useful, and that the use will reveal itself more easily once you have a basic grasp of the material.

Most basic algebra is constructive and you can easily implement basic concepts to gain a better understanding, e.g. algorithms that check if a multiplication table is a group, an equation solver in a group, a program that checks if two algebraic structures are isomorphic etc. Most of these problems have brute-force solutions which are easy to implement, but slow. The more you learn about algebra, the more algorithmic shortcuts you can make, to speed up your programs. E.g. the famous Miller-Rabin and AKS primality tests.

Check out this book by Rudolf Lidl and Harald Niederreiter: Introduction to Finite Fields and its Applications (2nd edition, 1994) http://www.amazon.com/Introduction-Finite-Fields-their-Applications/dp/0521460948

Quoting the book description in Amazon: "The theory of finite fields is a branch of modern algebra that has come to the fore in recent years because of its diverse applications in such areas as combinatorics, coding theory, cryptology and the mathematical study of switching circuits."

Besides cryptography, a very nice practical application of algebra in computer science is perhaps the implementaion of fractions, where numerator and denominator are of an integral or "big integer" type and encoding length is kepts small by reducing fractions (i.e. factoring out the greatest common divisor of numerator and denominator).

Concerning "big integer" data types, an interesting result is the so-called "Chinese remainder theorem" which permits the parallelization of integer operations once a representation as prime factors of the arguments are known.

Furthermore, most of the stuff found in algebra can be aesthetically pleasing (just a personal point of view).

• I don't see how this addresses the question? – András Salamon Feb 25 '13 at 9:34