On reducing factorization to the discrete logarithm problem modulo a composite |
| |
Authors: | Jacek Pomyka?a Bartosz ?ra?ek |
| |
Affiliation: | 1. Institute of Mathematics, Warsaw University, Banacha 2, 02-097, Warszawa, Poland
|
| |
Abstract: | The discrete logarithm problem modulo a composite??abbreviate it as DLPC??is the following: given a (possibly) composite integer n??? 1 and elements ${a, b \in \mathbb{Z}_n^*}$ , determine an ${x \in \mathbb{N}}$ satisfying a x ?=?b if one exists. The question whether integer factoring can be reduced in deterministic polynomial time to the DLPC remains open. In this paper we consider the problem ${{\rm DLPC}_\varepsilon}$ obtained by adding in the DLPC the constraint ${x\le (1-\varepsilon)n}$ , where ${\varepsilon}$ is an arbitrary fixed number, ${0 < \varepsilon\le\frac{1}{2}}$ . We prove that factoring n reduces in deterministic subexponential time to the ${{\rm DLPC}_\varepsilon}$ with ${O_\varepsilon((\ln n)^2)}$ queries for moduli less or equal to n. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|