Abstract
In this paper, we present several baby-step giant-step algorithms for the low hamming weight discrete logarithm problem. In this version of the discrete log problem, we are required to find a discrete logarithm in a finite group of order approximately $2^m$, given that the unknown logarithm has a specified number of 1âs, say $t$, in its binary representation. Heiman and Odlyzko presented the first algorithms for this problem. Unpublished improvements by Coppersmith include a deterministic algorithm with complexity $O \left ( m \left (\begin {smallmatrix}m / 2 t / 2\end {smallmatrix}\right ) \right )$, and a Las Vegas algorithm with complexity $O \left ( \sqrt {t} \left (\begin {smallmatrix}m / 2 t / 2\end {smallmatrix} \right )\right )$. We perform an average-case analysis of Coppersmithâs deterministic algorithm. The average-case complexity achieves only a constant factor speed-up over the worst-case. Therefore, we present a generalized version of Coppersmithâs algorithm, utilizing a combinatorial set system that we call a
Keywords
MathematicsIterated logarithmDiscrete logarithmLogarithmCombinatoricsHamming weightAlgorithmHamming distanceHamming codeDiscrete mathematicsBinary numberArithmeticComputer science
Affiliated Institutions
Related Publications
All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
Weighted paths in directed grid graphs of dimension (m X n) can be used to model the string edit problem, which consists of obtaining optimal (weighted) alignments between subst...
Improved time bounds for near-optimal sparse Fourier representations
•We study the problem of finding a Fourier representation <b>R </b>of <i>m</i> terms for a given discrete signal <b>A</b> of length<i> N</i>. The Fast Fourier Transform (FFT) ca...
The minimum distance problem for two-way entanglement purification
Entanglement purification takes a number of noisy EPR pairs and processes them to produce a smaller number of more reliable pairs. If this is done with only a forward classical ...
Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
Recently, several algorithms using number field sieves have been given to factor a number n in heuristic expected time $L_n [1/3; c]$, where \[ L_n [ v ;c ] = \exp \left\{ ( c +...
An Extremal Problem in Probability Theory
Let $\xi _1 ,\xi _2 , \cdots \xi _n $ be independent random variables satisfying the following condition; \[ {\bf M}\xi _k = 0,\quad \left| {\xi _k } \right| \leqq c,\quad 1 \le...
Publication Info
- Year
- 2001
- Type
- article
- Volume
- 71
- Issue
- 237
- Pages
- 379-392
- Citations
- 66
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
66
OpenAlex
Cite This
Douglas R. Stinson
(2001).
Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem.
Mathematics of Computation
, 71
(237)
, 379-392.
https://doi.org/10.1090/s0025-5718-01-01310-2
Identifiers
- DOI
- 10.1090/s0025-5718-01-01310-2