Applied Algebra: Codes, Ciphers, and Discrete Algorithms

Emphasizing the fact that solid mathematics leads to solid applications, this book builds a mathematical foundation that includes topics in number theory and the theory of infinite fields. It includes time-locked versions of Scientific Notebook and MuPAD that will help professionals quickly get up to speed. Chapter topics cover integers and computer algebra, codes, Euclidean algorithm, ciphers, error control codes, Chinese remainder theorem, theorems of Fermat and Euler, public key ciphers, finite fields, error-correcting codes, advanced encryption standard, and polynomial algorithms and fast fourier transforms. For data security officers.

Applied Algebra: Codes, Ciphers, and Discrete Algorithms shows how to do the mathematics of data communications and data storage. Hints are included for using Scientific Notebook®, Maple®, or ®MuPAD to do the messy calculations and to help you understand these mathematical ideas. Two central issues are data security (how to make data visible only to friendly eyes) and data integrity (how to minimize data corruption).

This book is intended for a first course in applied algebra for juniors and seniors majoring in areas such as mathematics, computer science and electrical engineering. The content includes mathematically interesting methods for dealing with issues related to data security and data integrity—methods that are also practical and in widespread use. The primary mathematical tools are number theory and the theory of finite fields. The mathematics in this book is developed as needed, but students who have had a prior course in abstract algebra or linear algebra have found such background to be useful.

Cryptology is the study of data security. How can a bank be certain that a message to transfer $1,000,000 was actually sent by someone authorized to send such a message? Or consider a political crisis in a remote region of the world. It is vital that sensitive issues be discussed with government leaders back home. The crisis could be blown out of control if these conversations were intercepted by some third party. The messages must be bounced off of satellites and the signals can be captured by anyone with a simple satellite dish. How can the messages be scrambled in such a way that no third party can possibly decipher them, but yet the messages can be easily read by friends back home?

Issues of data integrity are handled by error-control codes. The first pictures transmitted from the back side of the Moon in the late 1960s were in black and white, and of poor quality. Vertical black streaks in the pictures represented lost data—lost because of interference from solar radiation. More recent pictures returned from much greater distances produced beautiful high-resolution color images with no apparent lost data, mostly the result of better software that not only detects but also automatically corrects errors caused by interference.

We will look at several algorithms that arise in the study of cryptology and error-control codes. Many of these algorithms will feature commonsense approaches to relatively simple problems such as computing large powers. Other algorithms will be based on mathematically interesting ideas. The authors believe that the best applications have solid mathematical underpinnings. The Rijndael algorithm described in Chapter 11 provides a beautiful example of such an application. Donald Knuth, Professor Emeritus of The Art of Computer Programming at Stanford University, stated, "... random numbers should not be generated with a method chosen at random:'

Those who become hooked on applied algebra will eventually need abstra6t algebra, and lots of it. This book attempts to show the power of algebra in a relatively simple setting. Instead of a general study of groups, we consider only finite groups of permutations. Just enough of the theory of finite fields is presented to allow us to construct the fields that are needed for some of the error-control codes and for the new Advanced Encryption Standard. The setting for nearly everything we do will be over the integers, or polynomials over the integers, or remainders modulo an integer or a polynomial.

Hints are provided for using Scientific Notebook, Maple and MuPAD in order to understand better the ideas developed in this book. By now, all of us tend to use a calculator for routine numerical calculations-even for balancing a checkbook. Now you can concentrate on the mathematical ideas and not be distracted by the computations.

Most of the exercises require explanations and not just numerical answers. Consequently, we provide complete solutions to selected exercises.

More information is available on the website. There you will find codes written in various languages that perform many of the algorithms described in this book and links to other sites that contain information about cryptology and error-control codes.