This (https://en.m.wikipedia.org/wiki/Discrete_logarithm) Wikipedia article confuses me. If you have the equation a = g^n (mod P), and g, P and a are all known, then how does a brute force solving for n algorithm run in exponential time, as this article states. Shouldn't it be linear, or am I reading this article wrong?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
This is due to the common misconception especially from the beginners of the computational complexity ; the number of elements or number of bits.
In computational complexity, the computational complexity is typically expressed as a function of the size $n$ (in bits) of the input, and the complexity is expressed as a function of $n$.
You may be right to consider since sorting algorithms are using the number of elements however the context is important; the number of bits is more natural in cryptography since we measure the security in bits.
Therefore it is exponential in the input size where the input is measured in bits.
Saying it is linear while considering the number of possible values is misleading in cryptography since you will end up a difficulty in agreement with the cryptographers. Therefore use number of bits.
answered Nov 22, 2021 at 11:37
$\begingroup$
$\endgroup$
1
It's linear to the number of possible values of $n$, which is exponential in size to the number of bits used to represent $n$ in binary.
-
$\begingroup$ Oh right I see. Thank you for your help. $\endgroup$ Commented Nov 22, 2021 at 3:22