Number Theory and Cryptography

Question

I am a math tutor at a community college, and I stopped in to ask one of the professors a question about crypto and he lent me a graduate level book on for a full year course in the title of this post. The book is way over my head, and assumes you already have taken elementary number theory and abstract algebra. I'm not asking for a crash course, but more of a syllabus for the crash course on which topics to cover so I can handle this book. Does anyone have any suggestions or questions about clarification? EDIT I am already strong in probability/statistics. The book is A Course in Number Theory and Cryptography. Springer-Verlag publishing. Trig and snippets of calculus are how far I have gotten. Do I need to learn the entirety of the prerequisite classes or can I get away with certain chapters/sections. I assume certain chapters feed into crypto while others feed into different topics.

Answer 1

The Graduate Texts in Mathematics brand is a good brand. They're generally pretty easy reads for textbooks. I looked at the Table of Contents on Amazon, and it looks pretty self-contained. Though since it's geared at graduate students and advanced undergraduates, I can understand why you might feel the coverage is insufficient.

I think the table of contents for chapters 1-2 provide a good study guide, if you don't find the book's treatment sufficient. Number Theory is the study of the integers. It sounds intimidating, but you've really been doing it at some level since grade school. Remember long division where you have remainders? That's what modular arithmetic encapsulates. A lot of basic number theory deals with divisibility. In terms of a good extra reference, I think a Kenneth Rosen's Elementary Number Theory text is a good book for this. It will also address other topics like quadratic residues and the discrete log problem. I'm pretty sure there is coverage of RSA and a couple other cryptosystems in there.

In terms of the Abstract Algebra, the big hitter is with finite fields. To understand what a field is, you first have to understand what a group is. A group is a set of elements with an associative operation. There is a unique identity in the group and every element in the group is invertible. So the integers over addition form a group. Here, the identity element is $0$. A group is called Abelian if the operator is commutative. That is, for all $a, b \in G$, $a + b = b + a$. So the integers over addition are commutative.

Now a field is a set of elements has two operations. We will call them addition and multiplication. The field is an Abelian group over addition. We refer to $0$ as the additive identity. The field is also an Abelian group over multiplication, but we ignore $0$ in the considerations. The identity on multiplication is $1$. Some good examples of fields are the real numbers, rational numbers, complex numbers, and $\mathbb{Z}_{p}$ (for $p$ a prime). If you look at the reals, note that $r * \frac{1}{r} = 1$, right? So $\frac{1}{r}$ is the multiplicative inverse of $r$. Notice that we cannot consider $0$ for multiplicative inverses as we cannot divide by $0$. The reals are invertible on addition just as the integers are.

In terms of books, Durbin's Modern Algebra text is a very introductory textbook, geared more towards sophomores and inexperienced juniors in mathematics. You may find it helpful and not so intimidating.

Hope this helps give you some direction and insights into what you're studying. Best of luck!

Answer 2

Do you know the book by Wade Trappe and Lawrence Washington: Introduction to Cryptography with Coding Theory? I think it is not too difficult and very readable. There is a very large number of examples, some which use computers.