Join Log in
Score:3
avatar Crypto

Time Complexity Of Solving DLog When g and P are known

in flag
Darcy Sutton

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?

265
0 + 0
Score:6
DannyNiu avatar Crypto
vu flag
DannyNiu

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.

0 + 0
in flag
Darcy Sutton
Oh right I see. Thank you for your help.
0
Reply
Score:4
kelalaka avatar Crypto
in flag
kelalaka

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.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.