Number theory for computing

Publication date 1 September 1999

This is an idiosyncratic book written in a racy style, starting from `what is number theory' and ending with `quantum cryptography'. There is plenty on who did what at where and when, but much less on how it is done. Thus there are reports on results obtained in 1999, although the description of such work is closer to journalism than academic writing. The first part of the book is on elementary number theory, delivered in the style of definitions, theorems and examples, with proofs given only for the simplest results. Take, for example, the distribution of primes. The reader is told that ``in fact it is not difficult to prove that almost all the positive integers are composite numbers; actually such a proof, based only on results due to Euler and without using ideas from Chebyshev, is rarely given in books. However, instead of backing his claim, the author chose to bring the reader speedily to the Riemann Hypothesis and the Hardy-Littlewood conjectures. Inevitably there is a complete lack of motivation, let alone real explanation, here. The second part of the book is on algorithmic number theory, which includes discussions on computational complexity and algorithms for primality testing, factorization and the computation of discrete logarithms, as well as quantum number theoretic algorithms. Statements such as ``The Fermat method (to factorise \(n\)) \(\dots\) is of complexity \(O\big((n+1)/2-\sqrt n \big)\) and ``It is clear that the above computation will need at most \(O(\log 9007)\) arithmetic operations may beg some readers to check the meaning for the \(O\)-notation. In as much as the theorems lack proofs, the algorithms have no implementations, and many readers will have little idea on how to tackle most of the procedures. Besides the misprints, there are also carelessly made statements. For~example, on page~168, the statement for the primality test may lead one to believe that a number is prime if a primitive root exists. Even if a statement such as ``there are some primes with arbitrarily large smallest primitive roots is not considered to be inaccurate, the author is definitely confusing the reader with ``According to the prime number theorem, it is not possible to have a method that computes \(\pi(x)\) with less than about \(x/\log x\) arithmetic operations, especially since he contradicts himself a few sentences later with ``In~1985, Lagarias, Miller and Odlyzko adapted the Meissel-Lehmer method and proved that it is possible to compute \(\pi(x)\) with \(O(x^{1/3}/\log x)\) operations. One wonders whether the author has really thought about the difference between the problems of the listing and the counting of prime numbers. The last part of the book is on applied number theory, and many readers will have met the topics on computer system design, cryptography and information security. To conclude, the reviewer believes the book may be a good read for those who are perhaps reasonably familiar with many of the topics being mentioned, and would like to know superficially some of the recent developments. However, to really learn something, readers will find it more profitable to consult instead the many other new textbooks and monographs dealing with the same subject matters.

Recommendations

Cited in

(7)

This page was built for publication: Number theory for computing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4258219)