
Cards , Codes , and Kangaroos
Lindsey R. BoskoDunbar

Mathematics Topic: Linear Algebra 
Application Areas: Numerical analysis, Games 

PREREQUISITES
Cyclic groups, generators, modular arithmetic, matrix
inverses, modular arithmetic and factoring functions
for a computer algebra system(e.g., forMaple, the functions
mod and ifactor, ifthen statements and forloops
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 DiffieHellman 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
