# How to measure the complexity of the discrete logarithm problem?

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.

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

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