2
$\begingroup$

I looked here. The answer basically says that to calculate the complexity of the logarithm problem we have to take the length of the number representing the size of the group into accounts. 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. So please give me an answer.

$\endgroup$
2
$\begingroup$

To clarify: I think you ask why we only consider the bitlength of the size of the group and not the actual size of the group for complexity estimates, at least that's what I try to answer.


Why don't we chose the size of the group as the argument?

We do.
It entirely depends on the conventions you want to use. If $q$ is the size of the group and $n\approx\log_2(q)$ (don't forget that $2^n\approx q$) the bitlength, then you can either write the effort needed for brute-force as $\mathcal O(2^n)$ or $\mathcal O(q)$, with the first being slightly less precise (but not to a point where it matters) and the second being the more accurate one. However the first one nicely shows how the effort needed grows exponentially while the second one may leave you with the impression it's linear at which point people may find it harder to understand "how that's hard, after all it grows only linearly".

Is there a criterion to know what argument to chose?

Basically whatever you want. If you want to be clear and know your audience understands what you're meaning anyways, use $q$ otherwise use $2^n$ to make it easier to understand.

$\endgroup$
  • $\begingroup$ I had a problem of the impact of choosing the right parameter on the problem's class. I got the answer here. $\endgroup$ – Nassim HADDAM Oct 22 '16 at 19:31

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.