A Deterministic Algorithm for the Discrete Logarithm Problem in a Semigroup

DOI10.1515/JMC-2021-0022MaRDI QIDQ6359194arXivFDO

Authors Simran Tinani, Joachim Rosenthal

Publication date 27 January 2021

Published in arXiv

Full work available at URL https://doi.org/10.1515/JMC-2021-0022

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Arithmetic theory of semigroups (20M13) Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

arXiv classification

cs.CCmath.GR

Abstract: The discrete logarithm problem in a finite group is the basis for many protocols in cryptography. The best general algorithms which solve this problem have time complexity of $mathcalO(sqrtNlogN)$, and a space complexity of $mathcalO(sqrtN)$ where $N$ is the order of the group. (If $N$ is unknown, a simple modification would achieve a time complexity of $mathcalO(sqrtN(logN{)}^2)$.) These algorithms require the inversion of some group elements or rely on finding collisions and the existence of inverses, and thus do not adapt to work in the general semigroup setting. For semigroups, probabilistic algorithms with similar time complexity have been proposed. The main result of this paper is a deterministic algorithm for solving the discrete logarithm problem in a semigroup. Specifically, let $x$ be an element in a semigroup having finite order $N_x$. The paper provides an algorithm, which, given any element $yinlanglexangle$, provides all natural numbers $m$ with $x^m=y$, and has time complexity $O(sqrt{N}_x(log{N}_x{)}^2)$ steps. The paper also gives an analysis of the success rates of the existing probabilistic algorithms, which were so far only conjectured or stated loosely.

This page was built for publication: A Deterministic Algorithm for the Discrete Logarithm Problem in a Semigroup

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6359194)