Applied Number Theory

This textbook effectively builds a bridge from basic number theory to recent advances in applied number theory. It presents the first unified account of the four major areas of application where number theory plays a fundamental role, namely cryptography, coding theory, quasi-Monte Carlo methods, and pseudorandom number generation, allowing the authors to delineate the manifold links and interrelations between these areas. Number theory, which Carl-Friedrich Gauss famously dubbed the queen of mathematics, has always been considered a very beautiful field of mathematics, producing lovely results and elegant proofs. While only very few real-life applications were known in the past, today number theory can be found in everyday life: in supermarket bar code scanners, in our cars' GPS systems, in online banking, etc. Starting with a brief introductory course on number theory in Chapter 1, which makes the book more accessible for undergraduates, the authors describe the four main application areas in Chapters 2-5 and offer a glimpse of advanced results that are presented without proofs and require more advanced mathematical skills. In the last chapter they review several further applications of number theory, ranging from check-digit systems to quantum computation and the organization of raster-graphics memory. Upper-level undergraduates, graduates and researchers in the field of number theory will find this book to be a valuable resource Preface 6 Contents 8 1 A Review of Number Theory and Algebra 12 1.1 Integer Arithmetic 12 1.2 Congruences 16 1.3 Groups and Characters 23 1.3.1 Abelian Groups 23 1.3.2 Characters 30 1.4 Finite Fields 34 1.4.1 Fundamental Properties 34 1.4.2 Polynomials 38 1.4.3 Constructions of Finite Fields 44 1.4.4 Trace Map and Characters 51 Exercises 54 2 Cryptography 58 2.1 Classical Cryptosystems 58 2.1.1 Basic Principles 58 2.1.2 Substitution Ciphers 61 2.2 Symmetric Block Ciphers 63 2.2.1 Data Encryption Standard (DES) 63 2.2.2 Advanced Encryption Standard (AES) 65 2.3 Public-Key Cryptosystems 67 2.3.1 Background and Basics 67 2.3.2 The RSA Cryptosystem 70 2.3.3 Factorization Methods 73 2.4 Cryptosystems Based on Discrete Logarithms 78 2.4.1 The Cryptosystems 78 2.4.2 Computing Discrete Logarithms 80 2.5 Digital Signatures 84 2.5.1 Digital Signatures from Public-Key Cryptosystems 84 2.5.2 DSS and Related Schemes 86 2.6 Threshold Schemes 88 2.7 Primality Tests 91 2.7.1 Fermat Test and Carmichael Numbers 91 2.7.2 Solovay-Strassen Test 94 2.7.3 Primality Tests for Special Numbers 97 2.8 A Glimpse of Advanced Topics 100 Exercises 105 3 Coding Theory 110 3.1 Introduction to Error-Correcting Codes 110 3.1.1 Basic Definitions 110 3.1.2 Error Correction 113 3.2 Linear Codes 117 3.2.1 Vector Spaces Over Finite Fields 117 3.2.2 Fundamental Properties of Linear Codes 120 3.2.3 Matrices Over Finite Fields 123 3.2.4 Generator Matrix 125 3.2.5 The Dual Code 128 3.2.6 Parity-Check Matrix 129 3.2.7 The Syndrome Decoding Algorithm 132 3.2.8 The MacWilliams Identity 135 3.2.9 Self-Orthogonal and Self-Dual Codes 138 3.3 Cyclic Codes 139 3.3.1 Cyclic Codes and Ideals 139 3.3.2 The Generator Polynomial 144 3.3.3 Generator Matrix 146 3.3.4 Dual Code and Parity-Check Matrix 149 3.3.5 Cyclic Codes from Roots 151 3.3.6 Irreducible Cyclic Codes 154 3.3.7 Decoding Algorithms for Cyclic Codes 157 3.4 Bounds in Coding Theory 162 3.4.1 Existence Theorems for Good Codes 162 3.4.2 Limitations on the Parameters of Codes 164 3.5 Some Special Linear Codes 168 3.5.1 Hamming Codes 168 3.5.2 Golay Codes 176 3.5.3 Reed-Solomon Codes and BCH Codes 179 3.6 A Glimpse of Advanced Topics 184 Exercises 191 4 Quasi-Monte Carlo Methods 195 4.1 Numerical Integration and Uniform Distribution 195 4.1.1 The One-Dimensional Case 195 4.1.2 The Multidimensional Case 214 4.2 Classical Low-Discrepancy Sequences 226 4.2.1 Kronecker Sequences and Continued Fractions 226 4.2.2 Halton Sequences 233 4.3 Lattice Rules 237 4.3.1 Good Lattice Points 237 4.3.2 General Lattice Rules 254 4.4 Nets and (t,s)-Sequences 261 4.4.1 Basic Facts About Nets 261 4.4.2 Digital Nets and Duality Theory 268 4.4.3 Constructions of Digital Nets 278 4.4.4 (t,s)-Sequences 297 4.4.5 A Construction of (t,s)-Sequences 304 4.5 A Glimpse of Advanced Topics 309 Exercises 313 5 Pseudorandom Numbers 317 5.1 General Principles 317 5.1.1 Random Number Generation 317 5.1.2 Testing Pseudorandom Numbers 322 5.2 The Linear Congruential Method 326 5.2.1 Basic Properties 326 5.2.2 Connections with Good Lattice Points 334 5.3 Nonlinear Methods 340 5.3.1 The General Nonlinear Method 340 5.3.2 Inversive Methods 350 5.4 Pseudorandom Bits 360 5.5 A Glimpse of Advanced Topics 369 Exercises 372 6 Further Applications 377 6.1 Check-Digit Systems 377 6.1.1 Definition and Examples 377 6.1.2 Neighbor Transpositions and Orthomorphisms 379 6.1.3 Permutations for Detecting Other Frequent Errors 382 6.2 Covering Sets and Packing Sets 387 6.2.1 Covering Sets and Rewriting Schemes 387 6.2.2 Packing Sets and Limited-Magnitude Error Correction 389 6.3 Waring's Problem for Finite Fields 391 6.3.1 Waring's Problem 391 6.3.2 Addition Theorems 393 6.3.3 Sum-Product Theorems 397 6.3.4 Covering Codes 401 6.4 Hadamard Matrices and Applications 404 6.4.1 Basic Constructions 404 6.4.2 Hadamard Codes 408 6.4.3 Signal Correlation 410 6.4.4 Hadamard Transform and Bent Functions 412 6.5 Number Theory and Quantum Computation 419 6.5.1 The Hidden Subgroup Problem 419 6.5.2 Mutually Unbiased Bases 423 6.6 Two More Applications 425 6.6.1 Benford's Law 425 6.6.2 An Application to Raster Graphics 428 Exercises 431 Bibliography 435 Index 443 Front Matter....Pages i-x A Review of Number Theory and Algebra....Pages 1-46 Cryptography....Pages 47-98 Coding Theory....Pages 99-183 Quasi-Monte Carlo Methods....Pages 185-306 Pseudorandom Numbers....Pages 307-366 Further Applications....Pages 367-424 Back Matter....Pages 425-442