Analysis of the necklace algorithm and its applications
Loading...
Authors
Matty, Douglas M.
Subjects
Advisors
Fredricksen, Harold M.
Date of Issue
1999-06
Date
June 1999
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
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.
Type
Thesis
Description
Series/Report No
Department
Applied Mathematics
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
vii, 45 p.;28 cm.
Citation
Distribution Statement
Rights
This 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.