Analysis of the Necklace Algorithm and Its Applications
Abstract
A commonly studied problem in the field of cryptography is the Discrete Logarithm Problem. This problem is also referred to as the "distance" problem. Basically, one would like to know where a particular binary n-tuple is in a list combining all of them, represented as powers of some primitive element, or equivalently what is the distance between a given pair of n-tuples in a similar representation. A de Bruijn sequence is a well-known periodic binary sequence in which every n-tuple from 0 to 2/n appears. Our goal is to better understand the "prefer-ones" de Bruijn sequence. Ultimately, we wish to understand where each of the binary n-tuples appears in that sequence. Using the Necklace Algorithm, the sequence of n-tuples can be generated. This list has some special properties that allow us to perform the required analysis to locate the n-tuples by an association into classes. We partition the binary n-tuples into necklace classes according to the longest substring of ones appearing on the n-tuple. We then count how many n-tuples appear in the sequence for the first time as members of a necklace class containing no longer strings of ones.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1999
- Accession Number
- ADA368532
Entities
People
- Douglas M. Matty
Organizations
- Naval Postgraduate School