Cryptology ePrint Archive: Report 2001/094
Slope packings and coverings, and generic algorithms for the discrete logarithm problem
M. Chateauneuf and A.C.H. Ling and D.R. Stinson
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
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.
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
of such algorithms, in the sense that any generic algorithm
existence of a certain slope packing or covering, and conversely.
Category / Keywords: foundations / discrete logarithm problem, combinatorial cryptography
Publication Info: preprint
Date: received 9 Nov 2001
Contact author: dstinson at uwaterloo ca
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Version: 20011109:205248 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]