Fifteen Eighty Four

Peter L. Montgomery’s contributions to the field of computational number theory had a direct impact on our day-to-day information security life by making various cryptographic operations, which form the foundation to secure our digital connections, more efficient. Many of these techniques have been named after its inventor: e.g. Montgomery curves, Montgomery ladder, and most famously Montgomery modular multiplication. If you have used a debit or credit card then chances are high you have used Montgomery multiplication to secure your transaction in combination with the RSA cryptosystem. This elegant and efficient method for computing modular multiplications avoids expensive divisions by using the property of modern computer architectures that multiplication and divisions by powers-of-two can be done extremely efficient. Two chapters in this book are dedicated to this technique, which is explained in detail, one focusing on software and one related to hardware implementations.

When Peter began working, at System Development Corporation (SDC), he programmed using punch cards on time-shared main frame computers. By the time he had retired from Microsoft Research, he had implemented and optimized arithmetic code that was running on the mobile processors in smartphones. Peter worked as a programmer from the earliest stages of software engineering when computers needed to be held in their own buildings until the era of ubiquitous computing where people carry computing devices in their pockets. Both his algorithmic and mathematical contributions and his work as a programmer were instrumental to these massive advances that spanned his career — a career of more than forty years, impressive by the standards of the software industry.

This book is a tribute to his scientific work. Every chapter in this book starts with an idea by Peter which made a significant contribution to the field of computational number theory or cryptography. This idea is explained in detail and the subsequent research which followed this invention over the years is summarized. Most of Peter’s contributions are inspired by the integer factorization problem, his main research interest since high school. Hence, multiple chapters are dedicated to various techniques how to factor integers. Another chapter is dedicated to Montgomery curves and related work: such curves are used in modern instantiations of key agreement protocols since they offer performance and security benefits over other types of elliptic curves. Hence, this book can serve both as reference material for cryptographers and security experts as well as a good introduction for computational number theory enthusiasts.

Find out more about Topics in Computational Number Theory Inspired by Peter L. Montgomery