9
$\begingroup$

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.

$\endgroup$
  • 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$ – David Richerby Oct 22 '16 at 16:40
  • $\begingroup$ I think it's better that way. :) $\endgroup$ – Nassim HADDAM Oct 22 '16 at 16:51
5
$\begingroup$

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}$.

$\endgroup$
  • $\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$ – Nassim HADDAM Oct 22 '16 at 18:27
  • 1
    $\begingroup$ You cannot choose the parameter in that case – the parameter is always the input length. $\endgroup$ – Yuval Filmus Oct 22 '16 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$ – Nassim HADDAM Oct 22 '16 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$ – Yuval Filmus Oct 23 '16 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$ – Yuval Filmus Oct 23 '16 at 6: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.