[Solved]: How to measure the complexity of the discrete logarithm problem?

Problem Detail: 

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.

Asked By : Nassim HADDAM

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64961

 Ask a Question

 Download Related Notes/Documents