0
$\begingroup$

Can the discret log problem be solved when the modulus is a hard to factor composite number, i.e. when modulus $n=p*q$, where $p$ and $q$ are two large prime numbers?

$\endgroup$
  • 1
    $\begingroup$ Is the problem solving for integer $x$ the equation $g^x\bmod n=a$, given integers $n$, $g$, $a$, with $n$ a large composite too difficult to factor (which implies $n$ is several hundreds bits)? Is there information about the order of $g$, or/and the maximum value of $x$, and/or more generally how instances of the problem are built when it comes to $g$, $a$, and/or $x$, and /or the choice of factors $p_i$ of $n$ (perhaps with $p_i-1$ having a large prime factor)? $\endgroup$ – fgrieu Sep 11 '18 at 7:14
  • $\begingroup$ The values of $g$, $n$ and $a$ are known. There is also known that $n$ is a large composite number hard to factor. In this conditions, can we efficiently find $x$ such that $g^x mod n = a$? $\endgroup$ – mip Sep 11 '18 at 7:17
1
$\begingroup$

The problem is solving for $x$ the equation $g^x\bmod n=a$, given integers $n$, $g$, $a$, with $n$ a large composite too difficult to factor (which implies $n$ is several hundreds bits). It is not stated how instances of the problem are generated.

That is hard at least for some instances of the problem. In particular, if one of the factor $p$ of $n$ is large (say, at least 1536-bit), and $p-1$ has a large factor $p_0$ (say, at least 256-bit), and the order of $g$ in $\Bbb Z_p^*$ is $p_0$ or a larger multiple, then an instance of the problem where $x$ was chosen at random in $[1,n/2]$ and $a$ computed as $g^x\bmod n=a$ is hard. Argument: ability to solve $g^x\bmod n=a$ for $x$ and knowledge of the factorization of $n$ trivially implies ability of solving $g^x\bmod p=a\bmod p$ for $x$ (modulo $p-1$), which is is believed hard; and lacking knowledge of the factorization of $n$ can only make the question's problem harder.

I conjecture without proof that the condition "$p$ large" can be replaced by the existing "$n$ too difficult to factor"; and that a random instance is hard.

Among the usual Discrete Logarithm methods, Baby-step/Giant-step and Pollard's Rho remain applicable, with cost $O(\sqrt x)$ multiplications modulo $n$ (and moderate memory for Pollard's Rho). That allows to solve instances with moderate $x$ (say 80-bit with a standard PC), but I see no better method to solve a random instance.

$\endgroup$
  • $\begingroup$ Wouldn't be simpler to factor with NFS and then to solve the logarithms through NFS-DL ? $\endgroup$ – Ruggero Sep 11 '18 at 9:51
  • $\begingroup$ @Ruggero: yes, if $n$ can be factored (with NFS or otherwise; the algorithm of choice depends on how $n$ is generated), then that helps immensely, and is likely the way to go. But the problem statement makes $n$ "hard to factor", and I have reformulated it as "too difficult to factor", precisely to exclude that avenue. $\endgroup$ – fgrieu Sep 11 '18 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.