HASHING IN COMPUTERSCIENCE, FIFTY YEARS OF SLICINGAND DICING -- CONTENTS -- PREFACE -- PART I: MATHEMATICAL PRELIMINARIES -- CHAPTER 1: Counting -- 1.1 THE SUM AND PRODUCT RULES -- 1.2 MATHEMATICAL INDUCTION -- 1.3 FACTORIAL -- 1.4 BINOMIAL COEFFICIENTS -- 1.5 MULTINOMIAL COEFFICIENTS -- 1.6 PERMUTATIONS -- 1.7 COMBINATIONS -- 1.8 THE PRINCIPLE OF INCLUSION-EXCLUSION -- 1.9 PARTITIONS -- 1.10 RELATIONS -- 1.11 INVERSE RELATIONS -- APPENDIX 1: Summations Involving Binomial Coefficients -- CHAPTER 2: Recurrence and Generating Functions -- 2.1 RECURSIONS -- 2.2 GENERATING FUNCTIONS -- 2.3 LINEAR CONSTANT COEFFICIENT RECURSIONS -- 2.4 SOLVING HOMOGENEOUS LCCRS USING GENERATING FUNCTIONS -- 2.5 THE CATALAN RECURSION -- 2.6 THE UMBRAL CALCULUS -- 2.7 EXPONENTIAL GENERATING FUNCTIONS -- 2.8 PARTITIONS OF A SET: THE BELL AND STIRLING NUMBERS -- 2.9 ROUCHÉ'S THEOREM AND THE LAGRANGE'S INVERSION FORMULA -- CHAPTER 3: Asymptotic Analysis -- 3.1 GROWTH NOTATION FOR SEQUENCES -- 3.2 ASYMPTOTIC SEQUENCES AND EXPANSIONS -- 3.3 SADDLE POINTS -- 3.4 LAPLACE'S METHOD -- 3.5 THE SADDLE POINT METHOD -- 3.6 WHEN WILL THE SADDLE POINT METHOD WORK? -- 3.7 SADDLE POINT BOUNDS -- 3.8 EXAMPLES OF SADDLE POINT ANALYSIS -- CHAPTER 4: Discrete Probability Theory -- 4.1 THE ORIGINS OF PROBABILITY THEORY -- 4.2 CHANCE EXPERIMENTS, SAMPLE POINTS, SPACES, AND EVENTS -- 4.3 RANDOM VARIABLES -- 4.4 MOMENTS-EXPECTATION AND VARIANCE -- 4.5 THE BIRTHDAY PARADOX -- 4.6 CONDITIONAL PROBABILITY AND INDEPENDENCE -- 4.7 THE LAW OF LARGE NUMBERS (LLN) -- 4.8 THE CENTRAL LIMIT THEOREM (CLT) -- 4.9 RANDOM PROCESSES AND MARKOV CHAINS -- CHAPTER 5: Number Theory and Modern Algebra -- 5.1 PRIME NUMBERS -- 5.2 MODULAR ARITHMETIC AND THE EUCLIDEAN ALGORITHM -- 5.3 MODULAR MULTIPLICATION -- 5.4 THE THEOREMS OF FERMAT2 AND EULER -- 5.5 FIELDS AND EXTENSION FIELDS -- 5.6 FACTORIZATION OF INTEGERS.

5.7 TESTING PRIMALITY -- CHAPTER 6: Basic Concepts of Cryptography -- 6.1 THE LEXICON OF CRYPTOGRAPHY -- 6.2 STREAM CIPHERS -- 6.3 BLOCK CIPHERS -- 6.4 SECRECY SYSTEMS AND CRYPTANALYSIS -- 6.5 SYMMETRIC AND TWO-KEY CRYPTOGRAPHIC SYSTEMS -- 6.6 THE APPEARANCE OF PUBLIC KEY CRYPTOGRAPHIC SYSTEMS -- 6.7 A MULTITUDE OF KEYS -- 6.8 THE RSA CRYPTOSYSTEM -- 6.9 DOES PKC SOLVE THE PROBLEM OF KEY DISTRIBUTION? -- 6.10 ELLIPTIC GROUPS OVER THE REALS -- 6.11 ELLIPTIC GROUPS OVER THE FIELD Zm,2 -- 6.12 ELLIPTIC GROUPS CRYPTOSYSTEMS -- 6.13 THE MENEZES-VANSTONE ELLIPTIC CURVE CRYPTOSYSTEM -- 6.14 SUPER SINGULAR ELLIPTIC CURVES -- PART II: HASHING FOR STORAGE: DATA MANAGEMENT -- CHAPTER 7: Basic Concepts -- 7.1 OVERVIEW OF THE RECORDS MANAGEMENT PROBLEM -- 7.2 A SIMPLE STORAGE MANAGEMENT PROTOCOL: PLAIN VANILLA CHAINING -- 7.3 RECORD-MANAGEMENT WITH SORTED KEYS -- CHAPTER 8: Hash Functions -- 8.1 THE ORIGIN OF HASHING -- 8.2 HASH TABLES -- 8.3 A STATISTICAL MODEL FOR HASHING -- 8.4 THE LIKELIHOOD OF COLLISIONS -- CHAPTER 9: Hashing Functions: Examples and Evaluation -- 9.1 OVERVIEW: THE TRADEOFF OF RANDOMIZATION VERSUS COMPUTATIONAL SIMPLICITY -- 9.2 SOME EXAMPLES OF HASHING FUNCTIONS -- 9.3 PERFORMANCE OF HASHING FUNCTIONS: FORMULATION -- 9.4 THE χ2-TEST -- 9.5 TESTING A HASH FUNCTION -- 9.6 THE MCKENZIE ET AL. RESULTS -- CHAPTER 10: Record Chaining with Hash Tables -- 10.1 SEPARATE CHAINING OF RECORDS -- 10.2 ANALYSIS OF SEPARATE CHAINING HASHING SEQUENCES AND THE CHAINS THEY CREATE -- 10.3 A COMBINATORIAL ANALYSIS OF SEPARATE CHAINING -- 10.4 COALESCED CHAINING -- 10.5 THE PITTEL-YU ANALYSIS OF EICH COALESCED CHAINING -- 10.6 TO SEPARATE OR TO COALESCE -- AND WHICH VERSION? THAT IS THE QUESTION -- CHAPTER 11: Perfect Hashing -- 11.1 OVERVIEW -- 11.2 CICHELLI'S CONSTRUCTION -- CHAPTER 12: The Uniform Hashing Model -- 12.1 AN IDEALIZED HASHING MODEL.

12.2 THE ASYMPTOTICS OF UNIFORM HASHING -- 12.3 COLLISION-FREE HASHING -- CHAPTER 13: Hashing with Linear Probing -- 13.1 FORMULATION AND PRELIMINARIES -- 13.2 PERFORMANCE MEASURES FOR LP HASHING -- 13.3 ALL CELLS OTHER THAN HTn−1 IN THE HASH-TABLE OF n CELLS ARE OCCUPIED -- 13.4 m-KEYS HASHED INTO A HASH TABLE OF n CELLS LEAVINGCELL HTn−1 UNOCCUPIED -- 13.5 THE PROBABILITY DISTRIBUTION FOR THE LENGTH OF A SEARCH -- 13.6 ASYMPTOTICS -- 13.7 HASHING WITH LINEAR OPEN ADDRESSING: CODA -- 13.8 A POSSIBLE IMPROVEMENT TO LINEAR PROBING -- CHAPTER 14: Double Hashing -- 14.1 FORMULATION OF DOUBLE HASHING -- 14.2 PROGRESSIONS AND STRIDES -- 14.3 THE NUMBER OF PROGRESSIONS WHICH FILL A HASH-TABLE CELL -- 14.3.1 Progression Graphs -- 14.4 DOMINANCE -- 14.5 INSERTION-COST BOUNDS RELATING UNIFORM AND DOUBLE HASHING -- 14.6 USUALLYDOUBLEHASH -- 14.7 THE UDH CHANCE EXPERIMENT AND THE COST TO INSERT THE NEXT KEY BY DOUBLE HASHING -- 14.8 PROOF OF EQUATION (14.12a) -- 14.9 USUALLYDOUBLEHASH′ -- 14.10 PROOF OF EQUATION (14.12b) -- CHAPTER 15: Optimum Hashing -- 15.1 THE ULLMAN-YAO FRAMEWORK -- 15.1.1 The Ullman-Yao Hashing Functions -- 15.1.2 Ullman-Yao INSERT(k) and SEARCH(k) -- 15.1.3 The Ullman-Yao Statistical Model -- 15.2 THE RATES AT WHICH A CELL IS PROBED AND OCCUPIED -- 15.3 PARTITIONS OF (i)SCENARIOS, (i)SUBSCENARIOS, AND THEIR SKELETONS -- 15.3.1 (i)Subscenarios -- 15.3.2 Skeletons -- 15.4 RANDOMLY GENERATED m-SCENARIOS -- 15.5 BOUNDS ON RANDOM SUMS -- 15.6 COMPLETING THE PROOF OF THEOREM 15.1 -- PART III: SOME NOVEL APPLICATIONS OF HASHING -- CHAPTER 16: Karp-Rabin String Searching -- 16.1 OVERVIEW -- 16.2 THE BASIC KARP-RABIN HASH-FINGERPRINT ALGORITHM -- 16.3 THE PLAIN VANILLA KARP-RABIN FINGERPRINT ALGORITHM -- 16.4 SOME ESTIMATES ON PRIME NUMBERS -- 16.5 THE COST OF FALSE MATCHES IN THE PLAIN VANILLA KARP-RABIN FINGERPRINT ALGORITHM.

16.6 VARIATIONS ON THE PLAIN VANILLA KARP-RABINFINGERPRINT ALGORITHM -- 16.7 A NONHASHING KARP-RABIN FINGERPRINT -- CHAPTER 17: Hashing Rock and Roll -- 17.1 OVERVIEW OF AUDIO FINGERPRINTING -- 17.2 THE BASICS OF FINGERPRINTING MUSIC -- 17.3 HAAR WAVELET CODING -- 17.4 MIN-HASH -- 17.5 SOME COMMERCIAL FINGERPRINTING PRODUCTS -- CHAPTER 18: Hashing in E-Commerce -- 18.1 THE VARIED APPLICATIONS OF CRYPTOGRAPHY -- 18.2 AUTHENTICATION -- 18.3 THE NEED FOR CERTIFICATES -- 18.4 CRYPTOGRAPHIC HASH FUNCTIONS -- 18.5 X.509 CERTIFICATES AND CCIT STANDARDIZATION -- 18.6 THE SECURE SOCKET LAYER (SSL) -- 18.7 TRUST ON THE WEB ··· TRUST NO ONE OVER 40! -- 18.8 MD5 -- 18.9 CRITICISM OF MD5 -- 18.10 THE WANG-YU COLLISION ATTACK -- 18.11 STEVEN'S IMPROVEMENT TO THE WANG-YU COLLISION ATTACK -- 18.12 THE CHOSEN-PREFIX ATTACK ON MD5 -- 18.13 THE ROGUE CA ATTACK SCENARIO -- 18.14 THE SECURE HASH ALGORITHMS -- 18.15 CRITICISM OF SHA-1 -- 18.16 SHA-2 -- 18.17 WHAT NOW? -- APPENDIX 18: Sketch of the Steven's Chosen Prefix Attack -- CHAPTER 19: Hashing and the Secure Distribution of Digital Media -- 19.1 OVERVIEW -- 19.2 INTELLECTUAL PROPERTY (COPYRIGHTS AND PATENTS) -- 19.3 STEGANOGRAPHY -- 19.4 BOIL, BOIL, TOIL AND ··· BUT FIRST, CAREFULLY MIX -- 19.5 SOFTWARE DISTRIBUTION SYSTEMS -- 19.6 WATERMARKS -- 19.7 AN IMAGE-PROCESSING TECHNIQUE FOR WATERMARKING -- 19.8 USING GEOMETRIC HASHING TO WATERMARK IMAGES -- 19.9 BIOMETRICS AND HASHING -- 19.10 THE DONGLE -- APPENDIX 19: Reed-Solomon and Hadamard Coding -- Exercises and Solutions -- INDEX.