Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Computational number theory
Das A., Chapman & Hall/CRC, Boca Raton, FL, 2013. 614 pp. Type: Book (978-1-439866-15-3)
Date Reviewed: Aug 5 2014

Number theory has been studied since the time of the ancient Greeks. It consists of the study of the properties of numbers, primarily integers, and algorithms used to manipulate them. For example, mathematicians have wondered why prime numbers occur the way they do, and why we cannot produce a formula to generate successive primes. They have explored ways to factor integers, which for large numbers is a computationally hard problem. Fermat conjectured that the integer equation xn + yn = zn has no solutions for n > 2. It was only 300 years later that this was proved. The proof takes more than a hundred pages and is likely understood by only a handful of people.

For most of its history, number theory had no useful applications. In the 1970s, the new field of digital communications identified a need for secure private transmission of information. Elements of number theory provided a theoretical basis for designing protocols that could easily encrypt and decrypt messages given the right knowledge between sender and receiver, but that would be very difficult for an eavesdropper to decrypt without that knowledge.

The subsequent intensive study of algorithms that can be implemented on computers yielded insights into algorithms and the related theory of computational complexity. Here, the investigation considers a particular problem, say factoring a large integer, and examines what algorithms might be used. As to complexity, the question to answer is, given an algorithm, how long will it take to find an answer? Some algorithms run in polynomial time; that is, given an integer of size n, the running time would be of order n raised to a fixed power. Other algorithms require exponential time, which means that as n grows, the running time grows much faster than it does for a polynomial-time algorithm.

Because of the high processing requirement to solve these types of problems, many different algorithms have been developed in the attempt to reduce the total processing. Some are deterministic, while others resort to probabilistic methods. Algorithms are classified into complexity classes based on formal mathematical analyses of their running time.

In this book, Das addresses these aspects with an informative and very clearly written text. The book provides the groundwork by covering in successive chapters arithmetic of integers, including how very large integers are processed with computers, finite fields, polynomials, and elliptic curves. From there, subsequent chapters cover how these fundamental concepts are used: testing if a number is a prime, factoring integers, and calculating discrete logarithms. In addition, a chapter is devoted to large sparse linear systems. This area is not part of number theory per se, but is very useful in creating efficient number theoretic algorithms, hence its inclusion. All of the above are used in public key cryptography, the major application of number theory today, which is covered in the last chapter.

In each chapter, the author presents the theory along with detailed illustrative examples, calculations, and program code using the open-source GP/PARI interpreter for number theoretic calculations. Numerous exercises at the end of each chapter provide practice for both the theoretical and practical levels. The latter has the reader use GP/PARI to implement running programs.

Voluminous references are provided, often with brief descriptions of the more historically famous mathematicians. The references, provided as footnotes, span the history of number theory over the centuries from 300 BC to the present time. An appendix provides background information on the mathematical concepts of algorithm complexity, discrete algebraic structures, linear algebra, and probability.

As to the orientation of the book, the author states that “the material presented in this book is designed to cater to the need and taste of engineering students in advanced undergraduate and beginning graduate levels.” Concepts are developed from basic principles on the assumption that the reader may not have had prior exposure to the theory or techniques. All in all, this is an estimable work as a course text for readers interested in but new to the area.

Reviewer:  G. R. Mayforth Review #: CR142585 (1410-0824)
Bookmark and Share
  Reviewer Selected
 
 
Number-Theoretic Computations (F.2.1 ... )
 
 
Public Key Cryptosystems (E.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Number-Theoretic Computations": Date
The little book of big primes
Ribenboim P., Springer-Verlag New York, Inc., New York, NY, 1991. Type: Book (9780387975085)
Aug 1 1992
An almost linear-time algorithm for the dense subset-sum problem
Galil Z., Margalit O. SIAM Journal on Computing 20(6): 1157-1189, 1991. Type: Article
Mar 1 1993
Number theory in science and communication
Schroeder M., Springer-Verlag New York, Inc., New York, NY, 1984. Type: Book (9789780387121642)
Sep 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy