Book Review: “A Computational Introduction to Number Theory and Algebra” by Victor Shoup, 2nd ed.

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.

About these ads

17 comments

  1. I remember reading about this way back like 2007 or so…

  2. Good Job on the articles you have here, thank you for putting your time into it!

  3. Heh am I actually the only reply to this amazing read?!?

  4. 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.

  5. 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.

  6. 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.

  7. “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.

  8. 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.

  9. 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.

  10. 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.

  11. 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.

  12. 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.

  13. 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.

  14. 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.

  15. 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.

  16. 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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 44 other followers

%d bloggers like this: