Top

Amazon no longer offers textbook rentals. We do!

Hashing in Computer Science Fifty Years of Slicing and Dicing

by: Konheim, Alan G.

Hashing in Computer Science Fifty Years of Slicing and Dicing

by: Konheim, Alan G.

ISBN 13:
9780470630617
ISBN 10:
0470630612
Edition: 1st
Format: eBook
Copyright: 07/30/2010
Publisher: Wiley-Interscience

Rent

Sorry, this item is currently unavailable.

Free Shipping On Every Order

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

Extend or Purchase Your Rental at Any Time

Need to keep your rental past your due date? At any time before your due date you can extend or purchase your rental through your account.

Hashing in Computer Science Fifty Years of Slicing and Dicing > ISBN13: 9780470630617

Summary

Written by one of the developers of the technology, Hashing is both a historical document on the development of hashing and an analysis of the applications of hashing in a society increasingly concerned with security. The material in this book is based on courses taught by the author, and key points are reinforced in sample problems and an accompanying instructor s manual. Graduate students and researchers in mathematics, cryptography, and security will benefit from this overview of hashing and the complicated mathematics that it requires.

Author Biography

Alan G. Konheim, PhD, is Professor Emeritus of Computer Science at the University of Californa, Santa Barbara. Dr. Konheim’s early work at IBM led to the Data Encryption Standard (DES), which was evaluated by his Yorktown Probability and Cryptography Group. DES was certified as a national standard in the 1970s. Dr. Konheim continues to consult the government in the area of cryptanalysis.

PREFACE.

PART I: MATHEMATICAL PRELIMINARIES.

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.

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.

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: The Saddle Point Bounds.

3.8: Examples of Saddle Point Analysis.

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.

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 Fermat and Euler.

5.5: Fields and Extension Fields.

5.6: Factorization of Integers.

5.7: Testing Primality.

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 Z_{m,2 .}

_{6.12: Elliptic Group Cryptosystems.}

6.13: The Menezes-Vanstone Elliptic Curve Cryptosystem.

6.14: Super-Singular Elliptic Curves.

PART II: HASHING FOR STORAGE: DATA MANAGEMENT.

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.

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.

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 Hash Functions: Formulation.

9.4: The X²-Test.

9.5: Testing a Hash Function.

9.6: The McKenzie et al. Results.

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.

11. Perfect Hashing.

11.1: Overview.

11.2: Chichelli’s Construction.

12. The Uniform Hashing Model.

12.1: An Idealized Hashing Model.

12.2: The Asymptotics of Uniform Hashing.

12.3: Collision-Free Hashing.

13. Hashing with Linear Probing.

13.1: Formulation and Preliminaries.

13.2: Performance Measures for LP Hashing.

13.3: All Cells Other than HT_n-1 in the Hash-Table of n Cells are Occupied.

13.4: m-Keys Hashed into a Hash Table of n Cells Leaving Cell HT_n-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.

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).

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.

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-Rabin Fingerprint Algorithm.

16.7: A Nonhashing Karp-Rabin Fingerprint.

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.

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.

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.

Supplemental Materials

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.