Cards, Codes, and Kangaroos (UMAP)

PREREQUISITES

Cyclic groups, generators, modular arithmetic, matrix inverses, modular arithmetic and factoring functions for a computer algebra system(e.g., for Maple, the functions mod and ifactor, if-then statements and for-loops in programming in such a system, expected value, and standard results about Markov chains (transient and absorbing states, canonical form of the transition matrix, and the fundamental matrix).

ABSTRACT

The Kruskal Count is a card trick invented by mathematician (not magician) Martin Kruskal. The mathematics of the trick illustrates Pollard's kangaroo method, which was designed to solve the discrete logarithm problem: Given a finite cyclic group, G = hgi, and X 2 G, find x 2 Z such that gx = X. In this Module, we demonstrate the card trick and in revealing its secret, we uncover connections to the discrete logarithm problem, cryptography, andMarkov chains.

Table of Contents

1. INTRODUCTION

2. A CARD TRICK

3. CRYPTOGRAPHY

3.1 Ciphertext
3.2 Diffie-Hellman Key Exchange Protocol
3.3 ElGamal Cryptosystem

4. POLLARD'S KANGAROOMETHOD FOR THE DLP
4.1 Jumping Kangaroos
4.2 Analysis of Pollard's Kangaroo Method
4.3 Hash Functions
4.4 The Secret

5. MARKOV CHAINS
5.1 Results about Markov Chains

6. A SIMPLIFIED KRUSKAL COUNT AS A MARKOV PROCESS

7. THE KRUSKAL COUNT
7.1 How to Increase the Chance of the Trick's Success
7.2 Estimating the Chance of Success

8. OTHER RESULTS AND OPEN PROBLEMS

9. CONCLUSION

10.ANSWERS TO EXERCISES

11. APPENDIX A: COMPUTER CODE

12.APPENDIX B: CONTINUATION OF PROOF REFERENCES

ACKNOWLEDGMENTS

ABOUT THE AUTHOR