International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Slope packings and coverings, and generic algorithms for the discrete logarithm problem

Authors:
M. Chateauneuf
A.C.H. Ling
D.R. Stinson
Download:
URL: http://eprint.iacr.org/2001/094
Search ePrint
Search Google
Abstract: We consider the set of slopes of lines formed by joining all pairs of points in some subset S of a Desarguesian affine plane of prime order, p. If all the slopes are distinct and non-infinite, we have a slope packing; if every possible non-infinite slope occurs, then we have a slope covering. We review and unify some results on these problems that can be derived from the study of Sidon sets and sum covers. Then we report some computational results we have obtained for small values of p. Finally, we point out some connections between slope packings and coverings and generic algorithms for the discrete logarithm problem in prime order (sub)groups. Our results provide a combinatorial characterization of such algorithms, in the sense that any generic algorithm implies the existence of a certain slope packing or covering, and conversely.
BibTeX
@misc{eprint-2001-11506,
  title={Slope packings and coverings, and generic algorithms for the discrete logarithm problem},
  booktitle={IACR Eprint archive},
  keywords={foundations / discrete logarithm problem, combinatorial cryptography},
  url={http://eprint.iacr.org/2001/094},
  note={preprint dstinson@uwaterloo.ca 11635 received 9 Nov 2001},
  author={M. Chateauneuf and A.C.H. Ling and D.R. Stinson},
  year=2001
}