id: 06333924
dt: b
an: 2015e.00564
au: Forster, Otto
ti: Algorithmic number theory. (Algorithmische Zahlentheorie.) 2nd revised and
extended ed.
so: Heidelberg: Springer Spektrum (ISBN 978-3-658-06539-3/pbk;
978-3-658-06540-9/ebook). viii, 314~p. (2015).
py: 2015
pu: Heidelberg: Springer Spektrum
la: DE
cc: F65
ut: elementary number theory; factorization of integers; primality testing;
arithmetic algorithms; continued fractions; fast Fourier transform;
number fields
ci: Zbl 0870.11001; Zbl 0596.10006; Zbl 1071.11070
li: doi:10.1007/978-3-658-06540-9
ab: The author’s popular German textbook on computational number theory first
appeared almost twenty years ago [Algorithmische Zahlentheorie.
Braunschweig: Vieweg (1996; Zbl 0870.11001)]. As the reviewer of the
original edition (J. Wolfart) pointed out, this monograph was the first
introductory text on number theory that successfully combined the
theoretical and the computational aspects of the subject, thereby
reflecting the recent tendencies in number theory in a highly original
manner. The book under review is the second, revised and substantially
amplified edition of this unique text, the aim of which is to provide a
presentation of the basics of elementary number theory from the
abstract algebraic viewpoint, on the one hand, and via the
constructive, algorithmic approach on the other. As for the latter, a
special feature of the book is the description of many algorithms by
the interactive, multi-precision interpreter ARIBAS with PASCAL-like
syntax, which was developed by the author himself. A short introduction
to ARIBAS is given in an appendix, and this should enable the reader to
test the concrete arithmetic algorithms effectively on her/his own
personal computer, thereby deepening her/his understanding of the
matter through active explorations and experiments. Concerning the
prerequisites for studying this outstanding primer on both abstract and
algorithmic number theory, the basic knowledge of the elementary
abstract algebra of groups, rings, and fields as well as a little
familiarity with programming techniques (perhaps in PASCAL or C) should
absolutely suffice for this purpose. Compared to the first edition of
the book from 1996, various communicated errors and misprints have been
corrected. Moreover, and even more importantly, three new chapters have
been added, and the text as a whole has been slightly revised here and
there. Among the new topics taken up in the current edition are the
following: { indent8mm \item{(1)} a modern arithmetic factorization
method based on the multi-polynomial quadratic sieve (after [{\it C.
Pomerance\/}, EUROCRYPT ‘84, Lect. Notes Comput. Sci. 209, 169‒182
(1985; Zbl 0596.10006)]); \item{(2)} the discrete logarithm problem in
arithmetic and cryptography, including effective algorithms in this
context; \item{(3)} the deterministic AKS-primality test in polynomial
running time (after [{\it M. Agrawal\/} et al., Ann. Math. (2) 160, No.
2, 781‒793 (2004; Zbl 1071.11070)]). } Altogether, the present
second edition of the author’s textbook now comprises thirty
chapters, in which the reader is led from elementary divisibility
theory for integers up to the arithmetic in quadratic number fields,
with particular emphasis on concrete algorithmic methods, instructive
examples, and applications in cryptography. More precisely, the
following chapters form the contents of the book: 1. The Peano axioms;
2. The arithmetic operations; 3.~The Fibonacci numbers; 4.~The
Euclidean algorithm; 5.~The prime decomposition; 6.~The ring
$\mathbb{Z}/m\mathbb{Z}$; 7.~The theorems of Fermat, Euler and Wilson;
8.~The structure of the group $(\mathbb{Z}/m\mathbb{Z})^\ast$ and
primitive roots of unity; 9.~Pseudo-random generators; 10.~The inverse
of Fermat’s theorem; 11.~Quadratic residues and the quadratic
reciprocity law; 12.~Probabilistic primality tests; 13.~The Pollard
Rho-method; 14.~The $(p-1)$-factorization method; 15. ~The
RSA-cryptography method; 16.~Quadratic field extensions; 17.~The
$(p+1)$-primality test and Mersenne primes; 18.~The
$(p+1)$-factorization method; 19.~The fast Fourier transform;
20.~Factorization with the quadratic sieve (new!); 21.~The discrete
logarithm (new!); 22.~Elliptic curves; 23.~Factorization using elliptic
curves; 24.~Quadratic number fields; 25.~Lagrange’s four squares
theorem; 26.~Continued fractions; 27.~Pell’s equation; 28.~Ideal
classes in quadratic number fields; 29.~Factorization via the class
group of an imaginary-quadratic number field; 30.~The AKS-primality
test (new!). Apart from the already mentioned short introduction to the
multi-precision interpreter ARIBAS, there is a rich bibliography
concerning related textbooks, monographs, conference proceedings, and
research articles. With regard to the new, updating chapters of the
book, the list of references has been updated, too, and a few recent
textbooks have been added as well. Summing up, the unique character of
this utmost lucid and inviting textbook on elementary number theory has
been further augmented through the current second, revised and enlarged
edition. Now as before, the guiding principle of the entire approach is
the treatment of effective algorithms for factorization and primality
testing, and many classical concepts and results in number theory are
reconsidered from this methodological point of view. Without any doubt,
this fine textbook certainly (and finally) deserves a translation into
English, which would be for the benefit of much more interested
students and instructors worldwide.
rv: Werner Kleinert (Berlin)