A computational introduction to number theory and algebra

By Victor Shoup. 2005

726 citations recorded by the source corpus.

This introductory book emphasizes algorithms and applications, such as cryptography and error correcting codes, and is accessible to a broad audience. The presentation alternates between theory and applications in order to motivate and illustrate the mathematics. The mathematical coverage includes the basics of number theory, abstract algebra and discrete probability theory. This edition now includes over 150 new exercises, ranging from the routine to the challenging, that flesh out the material presented in the body of the text, and which further develop the theory and present new applications. The material has also been reorganized to improve clarity of exposition and presentation. Ideal as a textbook for introductory courses in number theory and algebra, especially those geared towards computer science students.

Subfields: Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/8ecb900b992a4d55cd1033f672a342dca63d3c05

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

Citations in the corpus

Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers (2021, neutral): “The second step is simply inverting the denominator of this rational function (mod x) and multiplying by the numerator, both of which are operations that need L log(L) time by standard results for polynomial arithmetic [51].”
Privacy-Preserving Set Operations (2005, methodology): “Finally, we overview the applications of these techniques explored in the rest of the chapter.”
Power-Up SRAM State as an Identifying Fingerprint and Source of True Random Numbers (2009, neutral): “in the most probable power-up state of the SRAM [33]:”
A Survey of Homomorphic Encryption for Nonspecialists (2007, background): “The reader may refer to [15] for more information concerning those we could not introduce properly, or algorithmic problems related to their computation.”
The Algorithm Design Manual (2020, background): “More general surveys of computational number theory include Bach and Shallit [BS96] and Shoup [Sho05].”
Introduction to Modern Cryptography, Second Edition (2014, neutral): “The texts by Wagstaff [173], Shoup [159], Crandall and Pomerance [51], Joux [96], and Galbraith [69] provide further information on algorithms for factoring and computing discrete logarithms, including descriptions of the (general) number field sieve.”
On Ideal Lattices and Learning with Errors over Rings (2010, neutral): “(Note that this factorization can be computed efﬁciently [Sho09, Chapter 20].)”
Constant-Round Privacy Preserving Multiset Union (2013, methodology): “However, our protocol performs operations over Fqd , hence two exponentiations involve a constant number of multiplications over Fqd , which take O(dlog2 3) using Karatsuba method or O(d log d log log d) by fast Fourier transform (FFT) [22].”