Lifting of solutions of an exponential congruence
type: Item
instance of: scholarly article
title: Lifting of solutions of an exponential congruence
zbMATH Open document ID: 1119.11072
author: I. A. Popovyan
published in: Mathematical Notes
publication date: 2007-05-21T00:00:00Z
review text: Let \(K\) be a finite extension of \(\mathbb Q\), \(n=[K:{\mathbb Q}]\), and \({\mathbb Z}_K\) be the ring of integers of \(K\). Let \(\mathfrak p\) be a prime ideal of \({\mathbb Z}_K\), and \(\alpha,\beta\in{\mathbb Z}\) be such that \(\alpha,\beta\in{\mathfrak p}\). In the paper a polynomial algorithm is suggested for reducing the discrete logarithm problem, i.e. of reducing the solution of the congruence \(\alpha^x\equiv \beta \bmod{{\mathfrak p}^N}\), \(N>1\) an integer, to the solution of the \(\alpha^x\equiv \beta \bmod{{\mathfrak p}}\), \(x\in {\mathbb Z}\). The solution is divided into three parts: the ``degenerate'' case in which \(\alpha\) is a root of degree \(p^f-1\) of \(1\) \(\bmod{ {\mathfrak p}^N}\), and the ``lower'' and ``higher'' cases in which \(N\) is not greater than \(\rho=\lfloor e/(p-1)\rfloor+1\) and greater that \(\rho\), with standard meaning of \(e,f\) and \(p\). In the presented explicit formulas instead of the Fermat quotients polynomially computable logarithmic functions are used, and \(\rho\) appears here because of the convergence of the series in use.
Mathematics Subject Classification ID: 11Y40
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11R21
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 5155498
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: discrete logarithm
zbMATH Keywords: ring of algebraic integers
zbMATH Keywords: Fermat quotient
zbMATH Keywords: p-adic logarithm
reviewed by: Štefan Porubský
MaRDI profile type: Publication
full work available at URL: s11006-006-0110-y
OpenAlex ID: W2069451805
cites work: Some soluble cases of the discrete logarithm problem
cites work: Q5302599
DOI: 10.1007/S11006-006-0110-Y
description: scientific article; zbMATH DE number 5155498