Analysis of the necklace algorithm and its applications
Matty, Douglas M.
Fredricksen, Harold M.
MetadataShow full item record
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.
RightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Ortiz, John E. (Monterey California. Naval Postgraduate School, 2006-09);Automated Guided Vehicles (AGVs) use different techniques to help locate their position with respect to a point of origin. This thesis compares two approaches that utilize a binary track laid on the floor for the AGV to ...
Bryant, Roy Dale (Monterey, California. Naval Postgraduate School, 1986-03);Random-like sequences of 0's and l's are generated efficiently by binary shift registers. The output of n-stage shift registers viewed as a sequence of binary n-tuples also give rise to a special graph called the de Bruijn ...
Fredricksen, Harold (SIAM (Society for Industrial and Applied Mathematics), 1982-04);Shift registers have been used to generate sequences of O’s and l’s for over thirty years. A wide variety of applications has been made of these sequences. Principally, communications have made use of the sequences ...