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 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.

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)

Short URL: ia.cr/2001/094

Discussion forum: Show discussion | Start new discussion