Computing a Discrete Logarithm in O(n³)

2009/12/11 by Charles Sauerbier, Sauerbier, Charles
Computer Science · Engineering · #Coding theory and cryptography #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #G.1.0 #Polynomial and algebraic computation #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.0912.2269

openalex publication_date 2009/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper presents a means with time complexity of at worst O(n³) to compute the discrete logarithm on cyclic finite groups of integers modulo p. The algorithm makes use of reduction of the problem to that of finding the concurrent zeros of two periodic functions in the real numbers. The problem is treated as an analog to a form of analog rotor-code computed cipher.

Related

• Hard Instances of Discrete Logarithm Problem and Cryptographic Applications
• Finding discrete logarithm in F_p^*
• Discrete logarithm problem in some families of sandpile groups
• A Deterministic Algorithm for the Discrete Logarithm Problem in a Semigroup
• Discrete logarithms in quasi-polynomial time in finite fields of fixed\n characteristic