Number Theory in Science and Communication : With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity

by Schroeder, Manfred Robert

• ISBN13: 9783540265962
• ISBN10: 3540265961
• Edition: 4th
• Format: Hardcover
• Copyright: 2005-12-16
• Publisher: Springer-Verlag New York Inc

Summary

"Number Theory in Science and Communication" is a well-known introduction for non-mathematicians to this fascinating and useful branch of applied mathematics . It stresses intuitive understanding rather than abstract theory and highlights important concepts such as continued fractions, the golden ratio, quadratic residues and Chinese remainders, trapdoor functions, pseudoprimes and primitive elements. Their applications to problems in the real world are one of the main themes of the book. This revised fourth edition is augmented by recent advances in primes in progressions, twin primes, prime triplets, prime quadruplets and quintruplets, factoring with elliptic curves, quantum factoring, Golomb rulers and "baroque" integers.From reviews of earlier editions '"I continue to find [Schroeder's] Number Theory a goldmine of valuable information. It is a marvellous book, in touch with the most recent applications of number theory and written with great clarity and humor.' Philip Morrison (Scientific American)"A light-hearted and readable volume with a wide range of applications to which the author has been a productive contributor ' useful mathematics outside the formalities of theorem and proof." Martin Gardner

Table of Contents

A Few Fundamentals
Introduction	p. 1
The Family of Numbers	p. 4
Fibonacci, Continued Fractions and the Golden Ratio	p. 7
Fermat, Primes and Cyclotomy	p. 9
Euler, Totients and Cryptography	p. 11
Gauss, Congruences and Diffraction	p. 13
Galois, Fields and Codes	p. 14
The Natural Numbers	p. 19
The Fundamental Theorem	p. 19
The Least Common Multiple	p. 20
Planetary "Gears"	p. 21
The Greatest Common Divisor	p. 21
Human Pitch Perception	p. 23
Octaves, Temperament, Kilos and Decibels	p. 24
Coprimes	p. 26
Euclid's Algorithm	p. 26
The Decimal System Decimated	p. 27
Primes	p. 28
How Many Primes are There?	p. 28
The Sieve of Eratosthenes	p. 29
A Chinese Theorem in Error	p. 30
A Formula for Primes	p. 31
Mersenne Primes	p. 32
Repunits	p. 36
Perfect Numbers	p. 37
Fermat Primes	p. 38
Gauss and the Impossible Heptagon	p. 39
The Prime Distribution	p. 41
A Probabilistic Argument	p. 41
The Prime-Counting Function [pi](x)	p. 43
David Hilbert and Large Nuclei	p. 47
Coprime Probabilities	p. 48
Primes in Progressions	p. 51
Primeless Expanses	p. 53
Squarefree and Coprime Integers	p. 54
Twin Primes	p. 54
Prime Triplets	p. 56
Prime Quadruplets and Quintuplets	p. 57
Primes at Any Distance	p. 58
Spacing Distribution Between Adjacent Primes	p. 61
Goldbach's Conjecture	p. 61
Sum of Three Primes	p. 63
Some Simple Applications
Fractions: Continued, Egyptian and Farey	p. 65
A Neglected Subject	p. 65
Relations with Measure Theory	p. 69
Periodic Continued Fractions	p. 70
Electrical Networks and Squared Squares	p. 73
Fibonacci Numbers and the Golden Ratio	p. 74
Fibonacci, Rabbits and Computers	p. 78
Fibonacci and Divisibility	p. 81
Generalized Fibonacci and Lucas Numbers	p. 81
Egyptian Fractions, Inheritance and Some Unsolved Problems	p. 85
Farey Fractions	p. 86
Farey Trees	p. 88
Locked Pallas	p. 92
Fibonacci and the Problem of Bank Deposits	p. 93
Error-Free Computing	p. 94
Congruences and the Like
Linear Congruences	p. 99
Residues	p. 99
Some Simple Fields	p. 102
Powers and Congruences	p. 103
Diophantine Equations	p. 106
Relation with Congruences	p. 106
A Gaussian Trick	p. 107
Nonlinear Diophantine Equations	p. 109
Triangular Numbers	p. 110
Pythagorean Numbers	p. 112
Exponential Diophantine Equations	p. 113
Fermat's Last "Theorem"	p. 113
The Demise of a Conjecture by Euler	p. 115
A Nonlinear Diophantine Equation in Physics and the Geometry of Numbers	p. 116
Normal-Mode Degeneracy in Room Acoustics (A Number-Theoretic Application)	p. 120
Waring's Problem	p. 121
The Theorems of Fermat, Wilson and Euler	p. 122
Fermat's Theorem	p. 122
Wilson's Theorem	p. 123
Euler's Theorem	p. 124
The Impossible Star of David	p. 125
Dirichlet and Linear Progression	p. 127
Cryptography and Divisors
Euler Trap Doors and Public-Key Encryption	p. 129
A Numercal Trap Door	p. 131
Digital Encryption	p. 132
Public-Key Encryption	p. 133
A Simple Example	p. 135
Repeated Encryption	p. 136
Summary and Encryption Requirements	p. 137
The Divisor Functions	p. 139
The Number of Divisors	p. 139
The Average of the Divisor Function	p. 142
The Geometric Mean of the Divisors	p. 142
The Summatory Function of the Divisor Function	p. 143
The Generalized Divisor Functions	p. 143
The Average Value of Euler's Function	p. 144
The Prime Divisor Functions	p. 146
The Number of Different Prime Divisors	p. 146
The Distribution of [omega](n)	p. 150
The Number of Prime Divisors	p. 151
The Harmonic Mean of [Omega](n)	p. 154
Medians and Percentiles of [Omega](n)	p. 156
Implications for Public-Key Encryption	p. 157
Certified Signatures	p. 158
A Story of Creative Financing	p. 158
Certified Signature for Public-Key Encryption	p. 158
Primitive Roots	p. 160
Orders	p. 160
Periods of Decimal and Binary Fractions	p. 163
A Primitive Proof of Wilson's Theorem	p. 166
The Index - A Number-Theoretic Logarithm	p. 166
Solution of Exponential Congruences	p. 167
What is the Order T[subscript m] of an Integer m Modulo a Prime p?	p. 169
Index "Encryption"	p. 170
A Fourier Property of Primitive Roots and Concert Hall Acoustics	p. 170
More Spacious-Sounding Sound	p. 172
Galois Arrays for X-Ray Astronomy	p. 174
A Negative Property of the Fermat Primes	p. 175
Knapsack Encryption	p. 177
An Easy Knapsack	p. 177
A Hard Knapsack	p. 178
Residues and Diffraction
Quadratic Residues	p. 181
Quadratic Congruences	p. 181
Euler's Criterion	p. 182
The Legendre Symbol	p. 183
A Fourier Property of Legendre Sequences	p. 185
Gauss Sums	p. 185
Pretty Diffraction	p. 187
Quadratic Reciprocity	p. 187
A Fourier Property of Quadratic-Residue Sequences	p. 188
Spread Spectrum Communication	p. 190
Generalized Legendre Sequences Obtained Through Complexification of the Euler Criterion	p. 191
Chinese and Other Fast Algorithms
The Chinese Remainder Theorem and Simultaneous Congruences	p. 194
Simultaneous Congruences	p. 194
The Sino-Representation: A Chinese Number System	p. 195
Applications of the Sino-Representation	p. 196
Discrete Fourier Transformation in Sino	p. 198
A Sino-Optical Fourier Transformer	p. 199
Generalized Sino-Representation	p. 200
Fast Prime-Length Fourier Transform	p. 201
Fast Transformation and Kronecker Products	p. 203
A Fast Hadamard Transform	p. 203
The Basic Principle of the Fast Fourier Transforms	p. 206
Quadratic Congruences	p. 207
Application of the Chinese Remainder Theorem (CRT)	p. 207
Pseudoprimes, Mobius Transform, and Partitions
Pseudoprimes, Poker and Remote Coin Tossing	p. 209
Pulling Roots to Ferret Out Composites	p. 209
Factors from a Square Root	p. 210
Coin Tossing by Telephone	p. 212
Absolute and Strong Pseudoprimes	p. 214
Fermat and Strong Pseudoprimes	p. 216
Deterministic Primality Testing	p. 216
A Very Simple Factoring Algorithm	p. 218
Factoring with Elliptic Curves	p. 218
Quantum Factoring	p. 219
The Mobius Function and the Mobius Transform	p. 220
The Mobius Transform and Its Inverse	p. 220
Proof of the Inversion Formula	p. 222
Second Inversion Formula	p. 223
Third Inversion Formula	p. 223
Fourth Inversion Formula	p. 224
Riemann's Hypothesis and the Disproof of the Mertens Conjecture	p. 224
Dirichlet Series and the Mobius Function	p. 225
Generating Functions and Partitions	p. 228
Generating Functions	p. 228
Partitions of Integers	p. 230
Generating Functions of Partitions	p. 231
Restricted Partitions	p. 232
Cyclotomy and Polynomials
Cyclotomic Polynomials	p. 236
How to Divide a Circle into Equal Parts	p. 236
Gauss's Great Insight	p. 239
Factoring in Different Fields	p. 243
Cyclotomy in the Complex Plane	p. 243
How to Divide a Circle with Compass and Straightedge	p. 244
Rational Factors of z[superscript N] - 1	p. 246
An Alternative Rational Factorization	p. 247
Relation Between Rational Factors and Complex Roots	p. 248
How to Calculate with Cyclotomic Polynomials	p. 249
Linear Systems and Polynomials	p. 251
Impulse Responses	p. 251
Time-Discrete Systems and the z Transform	p. 252
Discrete Convolution	p. 252
Cyclotomic Polynomials and z Transform	p. 253
Polynomial Theory	p. 254
Some Basic Facts of Polynomial Life	p. 254
Polynomial Residues	p. 255
Chinese Remainders for Polynomials	p. 256
Euclid's Algorithm for Polynomials	p. 257
Galois Fields and More Applications
Galois Fields	p. 260
Prime Order	p. 260
Prime Power Order	p. 260
Generation of GF (2[superscript 4])	p. 262
How Many Primitive Elements?	p. 264
Recursive Relations	p. 264
How to Calculate in GF(p[superscript m])	p. 266
Zech Logarithm, Doppler Radar and Optimum Ambiguity Functions	p. 267
A Unique Phase-Array Based on the Zech Logarithm	p. 270
Spread-Spectrum Communication and Zech Logarithms	p. 272
Spectral Properties of Galois Sequences	p. 273
Circular Correlation	p. 273
Application to Error-Correcting Codes and Speech Recognition	p. 275
Application to Precision Measurements	p. 277
Concert Hall Measurements	p. 278
The Fourth Effect of General Relativity	p. 279
Toward Better Concert Hall Acoustics	p. 280
Higher-Dimensional Diffusors	p. 285
Active Array Applications	p. 286
Random Number Generators	p. 287
Pseudorandom Galois Sequences	p. 288
Randomness from Congruences	p. 289
"Continuous" Distributions	p. 290
Four Ways to Generate a Gaussian Variable	p. 291
Pseudorandom Sequences in Cryptography	p. 292
Waveforms and Radiation Patterns	p. 293
Special Phases	p. 294
The Rudin-Shapiro Polynomials	p. 296
Gauss Sums and Peak Factors	p. 297
Galois Sequences and the Smallest Peak Factors	p. 299
Minimum Redundancy Antennas	p. 301
Golomb Rulers	p. 303
Number Theory, Randomness and "Art"	p. 305
Number Theory and Graphic Design	p. 305
The Primes of Gauss and Eisenstein	p. 307
Galois Fields and Impossible Necklaces	p. 308
"Baroque" Integers	p. 312
Self-Similarity, Fractals and Art
Self-Similarity, Fractals, Deterministic Chaos and a New State of Matter	p. 315
Fibonacci, Noble Numbers and a New State of Matter	p. 318
Cantor Sets, Fractals and a Musical Paradox	p. 324
The Twin Dragon: A Fractal from a Complex Number System	p. 329
Statistical Fractals	p. 331
Some Crazy Mappings	p. 333
The Logistic Parabola and Strange Attractors	p. 336
Conclusion	p. 339
Glossary of Symbols	p. 340
References	p. 343
Name Index	p. 355
Subject Index	p. 359
Table of Contents provided by Ingram. All Rights Reserved.