I wrote this review a few months ago for “Computing Reviews”, who’ve published it. But for the benefit of those who don’t have access to these reviews, here it is.

Occasionally it’s a pleasure to find a book which is so masterful, so well written, that it has all the hallmarks of the classic. This is such a book. Shoup has set himself a difficult task – to bring the reader up to speed with number theory and algebra, starting “from scratch” – and he has succeeded magnificently. My main complaint with the book is that it is not longer, but as Shoup himself regretfully observes in the introduction, to keep to a reasonable size, some important topics had to be omitted.

Many books on computational number theory present the theory as a sort of smorgasbord of algorithms: primality testing, factorization, discrete logarithms, modular square and n-th roots. Shoup steers clear of this recipe based approach, and instead places the entire theory into a formal algebraic setting. This allows not only for elegance of exposition and a remarkable clarity, but provides the entire book with a structural homogeneity.

Even though “some topics could simply not be covered”, the range of topics presented is wide. The book is geared towards students of cryptography and coding theory, and the material has been chosen to be most relevant to those disciplines.

The books starts with several of standard integer based number theory: divisibility, congruences and modular arithmetic, including quadratic residues (but reciprocity is treated later), large integer arithmetic, Euclid’s algorithm and its association with the Chinese remainder theorem, and a brief discussion of the RSA cryptosystem, including a particularly elegant proof of its correctness. All this material is standard to many other texts, yet rarely treated with as much care as here, in spite of the relative brevity. These first few chapters contain as much mathematics as many cryptography texts, and yet at this stage we are not yet one fifth into the book! Another chapter discusses the distribution of primes, including a proof of Bertrand’s postulate and a discussion of the prime number theorem. Given the importance of primes to modern cryptography, these may be considered vital topics, and it is refreshing to see them treated so well.

These first chapters set the scene, so to speak, for the number theory with which the text is concerned. However, much of the subsequent material is discussed in terms of the general theory of groups and rings. Primitive roots, for example, are not discussed as such, but in terms of generators of the non-zero residues of integers modulo a prime. Although this approach might seem at first to be unnecessarily obtuse, it is in fact the most natural way of introducing these algorithms, as it places them squarely in a generalized algebraic theory. The text, as we would expect, contains several chapters discussing the basic theory of abelian groups and rings, including a fine proof of the fundamental theorem of the structure of finite abelian groups as

a sum of cyclic groups.

What makes this book unique is the way that several different mathematical strands – number theory and algebra – are interwoven and made into a masterful whole. As well as rings and fields, there is much linear algebra (modules, vector spaces and matrices), as well as a considerable amount on probability distributions and probabilistic algorithms, culminating in the Miller-Rabin test for primality and a few applications.

The book ends with some chapters on finite fields and their various algorithms, and a chapter on the AKS deterministic primality test, for which the author carefully observes that the probabilistic Miller-Rabin test is much faster, and hence should be preferred for all practical purposes. However, as an ingenious use of much number theory and algebra, the AKS algorithm is a lovely example with which to finish the text.

Although the text requires not much specific mathematical background, I would hesitate to use it except in an advanced class, or for students whose mathematical ability was already high. The material moves swiftly – while never compromising rigour – and the multiple strands assume considerable ability on the part of the reader. I was pleased to see copious exercises; a student who has completed the book and mastered the exercises will be in a very strong position to embark on some advanced studies. The author does not recommend any specific chapter sequences for a semester’s study, but clearly an astute teacher could pull some parts from this text for an initial course of study, and complete the text in an advanced course.

One regrettable omission is that of the use of any computational tools, either the author’s own C++ NTL library for computational number theory and algebra, or the use of a computer algebra system. A companion volume, or material on the author’s website, discussing some implementation issues, would be most welcome. We note in passing that thanks to the generosity of the publishers, the entire text is available under a Creative Commons licence on the author’s site http://www.shoup.net.

This is a truly magnificent text, deserving of a place on the shelves of any mathematician or computer scientist working in these areas. I hope it has a long life and many further editions.

Filed under: Cryptography, Maths teaching

Harriet Wiln, on February 13, 2010 at 7:58 am said:I remember reading about this way back like 2007 or so…

Mariano Thorpe, on February 21, 2010 at 4:35 pm said:Good Job on the articles you have here, thank you for putting your time into it!

Shana Bermudez, on May 31, 2010 at 8:40 pm said:Heh am I actually the only reply to this amazing read?!?

directorwebd, on August 22, 2010 at 2:55 pm said:web director

amazon.de, on May 9, 2013 at 1:20 pm said:So how do you select the finest shop from all the retailers

that offer this camera. This 12 megapixel camera is capable of capturing 3D photos too.

This lets you manage exactly how wide the camera shutter

opens and the remaining settings are governed automatically to provide you with an excellent

picture.

Jimmie, on May 14, 2013 at 6:29 am said:If you find it a bit maddening to follow the daily fluctuations of the scale even though you

are eating properly, pick three days of the week on which you will

always weigh yourself (for example, Monday, Wednesday,

and Friday). Withdrawal from levothyroxine can be done but it takes

6 weeks of withdrawal for the remaining thyroid tissue to be completely starved.

The institution has persistently offered ideal programs and services for those struggling to achieve certain levels of body weight.

http://www.kuehtaile-alm.at/index.php?option=com_phocaguestbook&view=phocaguestbook&id=1&Itemid=69&lang=en, on June 8, 2013 at 7:48 am said:When it comes to fishing, some goes for fishing as an entertainment activity and many depends upon fishing for their livelihood.

Spinning – Trout are aggressive and definitely will strike and eat smaller fish.

Garmin Accuracy and Innovation Leads You to the Fish.

sirius xm radio, on June 13, 2013 at 12:44 pm said:“Worked All Zones Award” is the same concept with time

zones. Much of your best players marketplaces in the united

states are supervised. Whats more is that 2G

phones can come in a tinier and slimmer package, even its batteries.

gretchen wilson, on June 14, 2013 at 9:33 pm said:In other trick taking games, players can take tricks on a number of kind

of contract. If you are unable to sign in to Game Center

or are having problems staying connected:. Making your game play is the next phase you’ll be focusing on.

forum.wsk.tw, on July 17, 2013 at 10:06 am said:Too many folks have already thrown away plenty of good money

on nothing but useless salt tablets being shipped from South

America. Cucumber contains sterols which can help to

lower cholesterol and prevent carbohydrates from converting to body fat.

Now, the average healthy amount people are supposed to lose is 2 pounds per week.

emarnetwork.nl, on July 18, 2013 at 2:07 pm said:Even though your goal is just to lose 5 pounds in a week, you should be strict with what you do so as not to inadvertently undo all your hard work for vegetarian weight loss.

Vinson had participants keep their normal diet and exercise routines (or lack thereof) and merely

added the green coffee. Do not be tempted to lose weight as quickly as you can,

because a crash diet will have you eating less than a thousand calories a day

slowing down your metabolism.

http://bufor.org/, on July 30, 2013 at 1:50 pm said:Christmas is the celebration of the birth of Jesus

Christ. Line Dish with Wax Paper3) Line the bottom of the casserole dish with the wax paper.

This way, a slice can be removed from the freezer, defrosted, and eaten whenever the

urge for birthday cake hits.

Senaida, on August 2, 2013 at 5:39 am said:You don’t have to hit the gym for two and three hours each day to lose weight, but it does help to squeeze in 30 minutes of physical activity each day. Authorities inside the area will need to have an intensive understanding of laboratory and labeling techniques, infection security precautions, appropriate blood attract approaches to the elderly and for infants and even more. The institution has persistently offered ideal programs and services for those struggling to achieve certain levels of body weight.

http://thebrag.com/node/434747, on August 4, 2013 at 1:04 am said:s better to use whole foods made from scratch for good

health. Cucumber contains sterols which can help to lower cholesterol and prevent carbohydrates

from converting to body fat. Do not be tempted to lose weight as quickly as

you can, because a crash diet will have you eating less than a

thousand calories a day slowing down your metabolism.

Ellie, on August 4, 2013 at 4:23 am said:a Bruce Lee workout includes stretching, bending, running,

dipping, kicking, jumping, traditional muscle building exercises,

weight lifting, rope skipping, medicine ball handling, etc.

Authorities inside the area will need to have an intensive understanding of laboratory

and labeling techniques, infection security precautions,

appropriate blood attract approaches to the elderly and for infants and even more.

Many people don’t have the time to weight themselves every day, but checking the scale on a regular basis can definitely help when you’re working

to lose weight and keep it off.

http://richmombusiness.com/wahm-forum-work-at-home-mom-business-entrepreneur-how-to-get-more-traffic-to-your-site-using-pinterest, on August 7, 2013 at 12:25 am said:Believing that you are actually starving, it releases chemicals

that actually make it harder to lose weight in an effort to conserve

energy. Avocados- Although not my favorite, are high in fats,

the good ones. When you’re about to start on your weight loss plan, it’s a good idea to

think about your end goal and chunk it down into smaller goals.

volunteer programs, on March 22, 2014 at 12:34 am said:When someone writes an paragraph he/she maintains the plan of a user

in his/her brain that how a user can know it. Therefore that’s why

this piece of writing is perfect. Thanks!