Finding discrete logarithms with a set orbit distinguisher

Journal of mathematical cryptology

article

Robert P. Gallant¹ 

[1] Memorial University (Grenfell Campus)

关键词: Discrete logarithm problem;    complexity;    sparse polynomial;    quadratic residue codes;   

DOI  :  10.1515/jmc-2012-0002

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

Abstract. We consider finding discrete logarithms in a group of prime order p when the help of an algorithm D that distinguishes certain subsets of from each other is available. If the complexity of D is a polynomial, say , then we can find discrete logarithms faster than square-root algorithms. We consider two variations on this idea and give algorithms solving the discrete logarithm problem in with complexity and when has factors of suitable size. When multiple distinguishers are available and is sufficiently smooth, logarithms can be found in polynomial time. We discuss natural classes of algorithms D that distinguish the required subsets, and prove that for some of these classes no algorithm for distinguishing can be efficient. The subsets distinguished are also relevant in the study of error correcting codes, and we give an application of our work to bounds for error-correcting codes.

【 授权许可】

CC BY|CC BY-NC-ND