ON REDUCING FACTORIZATION TO THE DISCRETE LOGARITHM PROBLEM MODULO A COMPOSITE

摘要

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 ∈ Z_n~*, determine an x ∈ 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 DLPC_ε obtained by adding in the DLPC the constraint x ≤ (1-ε)n, where s is an arbitrary fixed number, 0 < ε ≤ 1/2. We prove that factoring n reduces in deterministic subexponential time to the DLPC_ε with O_ε((ln n)~2) queries for moduli less or equal to n.