The answers to this question on Crypto Stack Exchange basically says that, to measure the complexity of the logarithm problem, we have to take the length of the number representing the size of the group into account. It seems arbitrary, why don't we chose the size of the group as the argument? Is there a criterion to know what argument to chose? In fact, I know I overlooked something important since the complexity changes hugely if we do it by the size of the group.

  • 2
    $\begingroup$ Interesting question! I edited it to say "measure the complexity", rather than "calculate" it, since the answer to how we calculate it is ¯\_(ツ)_/¯. :-) $\endgroup$ Commented Oct 22, 2016 at 16:40
  • $\begingroup$ I think it's better that way. :) $\endgroup$ Commented Oct 22, 2016 at 16:51

1 Answer 1


It doesn't matter whether you choose the size of the group $|G|$ or the size of the integer representing it $n$ as a parameter, since $n \approx \log |G|$. There are two reasons that usually the complexity is described in terms of $n$ rather than $|G|$:

  1. $n$ is the length of the input (more accurately, the input has length $\Theta(n)$), and we usually measure the complexity of algorithms as a function of the input length.

  2. Usually $n$ is a small number such as $1024$, whereas $|G|$ is a huge number such as (roughly) $2^{1024}$.

  • $\begingroup$ I see your point, but doesn’t it make it a problem in P if we chose the size of the group as a parameter? $\endgroup$ Commented Oct 22, 2016 at 18:27
  • 1
    $\begingroup$ You cannot choose the parameter in that case – the parameter is always the input length. $\endgroup$ Commented Oct 22, 2016 at 18:28
  • $\begingroup$ Thanks for the answers. I had a problem with what might happen if we consider the other case (problems in P becoming in NP and the other way around). I can see clearly now :) . $\endgroup$ Commented Oct 22, 2016 at 19:25
  • 1
    $\begingroup$ We don't do the calculation in unary since our goal is to factor some number or to compute some discrete logarithm, and we don't care how the number is represented. Giving it as input in binary or unary doesn't affect the "wall time" needed for solving the problem, only its complexity in terms of the input size (since we are changing the input size!). $\endgroup$ Commented Oct 23, 2016 at 6:07
  • 1
    $\begingroup$ Besides, we cannot really have a 128-bit long integer as unary input to a real-world algorithm. There are not enough atoms in the universe. $\endgroup$ Commented Oct 23, 2016 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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