Yes, finding the discrete logarithm of $a$ to base $g$ modulo $p$ is solving for $x$ the equation $a=g^x\bmod p$ given integers $g$ (the base), $p$ (the modulus), and $a$ (which discrete logarithm $x$ is thought). That's known as the Discrete Logarithm Problem (modulo $p$).
The discrete logarithm of $a=3$ to base $g=2$ modulo $p=11$ is thus $x=8$, because $2^8=256=23\times11+3$ thus $2^8\bmod11=3$ [not because $2^3=8$ thus $2^3\bmod11=8$, which happens to also hold].
The security of the original Diffie-Hellman Key Exchange (using multiplication modulo $p$ as the group operation) requires that it's practically impossible to solve that problem. In practice, parameters $g$ and $p$, and the range in which $x$ is chosen secretly and at random before $a$ is computed as $g^x\bmod p$, are such that the DLP is intractable!
I'll discuss, from the ground up, what that problem is: and some standard methods to attempt to solve it. At first I'll only assume $p\in\mathbb N\setminus\{0,1,2\}$ and $g\in[1,p)$.
Definition: what's $g^x\bmod p$
For any $x\in\mathbb N$, by definition of $g^x$, that's $\underbrace {g\cdot g\ldots g}_{x\text{ terms }g}$, with $g^x=1$ when $x=0$ (since $g\ne 0$). That value $g^x$ is an integer (since $g$ is an integer).
And, by definition of the operator$\bmod$ (when there's neither an opening parenthesis immediately on it's left, nor a negative power in it's left operand), $g^x\bmod p$ is the uniquely defined $y$ in range $[0,p)$ such that $g^x-y$ is a multiple of $p$. That $y$ is an integer, and we want it to be the given $a$.
Range check of $a$
It follows that there can be a solution to $a=g^x\bmod p$ only if $a$ is an integer in $[0,p)$. In the following we'll assume this has been checked to hold.
Search by enumeration
Notice that for all $n\in\mathbb N$, it holds $g^{n+1}\bmod p=((g^n)\cdot g)\bmod p=(g^n\bmod p)\cdot g\bmod p$. This gives an efficient mean to compute $G_n=g^n\bmod p$ for incremental values of $n\in\mathbb N$, using that $G_0=1$ and the recurrence relation $G_{n+1}=G_n\cdot g\bmod p$. E.g.
- For $(g,p)=(2,11)$ the sequence goes 1, 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, 4, …
- For $(g,p)=(2,10)$ the sequence goes 1, 2, 4, 8, 6, 2, 4, 8, 6, 2, …
- For $(g,p)=(3,10)$ the sequence goes 1, 3, 9, 7, 1, 3, 9, …
- For $(g,p)=(2,8)$ the sequence goes 1, 2, 4, 0, 0, 0, …
That sequence $G_n$ consists of integers in $[0,p)$, thus is bound to cycle at one of it's earlier values after at worst $p$ steps. Thus a basic algorithm to solve for $x$ the equation $a=g^x\bmod p$ is:
- $x\gets 0$ and $G\gets 1$
- while $x<p$
- if $G=a$ then output "the smallest non-negative integer solution is " $x$, and stop.
- $x\gets x+1$ and $G\gets G\cdot g\bmod p$
- output "there is no solution", and stop.
In the worst case, this algorithm performs $p$ multiplication modulo $p$, thus has worst-case time complexity $\mathcal O(p\cdot\log^2p)$ using standard algorithms.
Composite $p$: Pohlig-Hellman
When $p$ is not a prime, and if we manage to fully factor $p$, we can use the Pohlig-Hellman algorithm. In a nutshell, the algorithm uses that having factored $p$ as $\prod{p_i}^{m_i}$, the Chinese Remainder Theorem allows to break the original equation $g^x\bmod p=a$ into simpler subproblems ${g_i}^x\bmod{p_i}^{m_i}=A_i$ with $g_i=g\bmod{p_i}^{m_i}$ and $A_i=a\bmod {p_i}^{m_i}$.
In the following I'll restrict to $p$ prime.
Prime $p$: further check of $a$, and a slight simplification
When $p$ is prime, the values taken by $G_n$ as defined above always cycle back at $1$, and first do so when $n$ is a certain integer defined as the order of $g$ modulo $p$, often noted $|g|$. That $|g|$ is such that $g^{|g|}\bmod p=1$ (and the smallest strictly positive such integer).
By Lagrange's theorem of group theory, $|g|$ is always a divisor of $p-1$. If we can factor $p-1$, we can compute $|g|$ reasonably efficiently. The general idea uses that we can compute $g^n\bmod p$ (modular exponentiation) with only $\mathcal O(\log n)$ modular multiplications. This allows checking $g^{(p-1)/k}\bmod p=1$ for various $k$. We first do so for $k=q_i$ among the primes dividing $p-1$, and if $g^{(p-1)/k}\bmod p\ne1$ for every of these we conclude that $|g|=p-1$; or, if we find a $k$ with $g^{(p-1)/k}\bmod p\ne1$, we can proceed with larger multiples of $k$ until we find $|g|$.
More often than not, $|g|$ is sizably smaller than $p$; sometime, much smaller. For example, when $(p,g)$ are chosen as in Clauss P. Schnorr's Efficient Signature Generation by Smart Cards, $p$ might have 155 decimal digits, but $|g|$ might have "only" 43 decimal digits†.
Knowing $|g|$ lets us perform a quick test to determine if there is a solution: there's one if and only if $a^{(p-1)/|g|}\bmod p=1$. Thus an alternate algorithm is:
- if $a^{(p-1)/|g|}\bmod p\ne 1$, then output "there is no solution", and stop.
- $x\gets 0$ and $G\gets 1$
- while $G\neq a$
- $x\gets x+1$ and $G\gets G\cdot g\bmod p$
- output "the smallest non-negative integer solution is " $x$, and stop.
Worst case complexity for known factorization of $p$ is $\mathcal O(|g|\cdot\log^2p+\log^4p)$ with $|g|<p$, for standard algorithms.
Baby-step/giant-step
Assume we know $|g|$. The baby-step/giant-step algorithm works as follows:
- if $a^{(p-1)/|g|}\bmod p\ne 1$, then output "there is no solution", and stop.
- $r\gets\left\lceil{\sqrt{|g|}}\,\right\rceil$
- $i\gets 0$ and $y\gets a$
- repeat
- enter $y$ and $i$ in a table allowing quick search of $y$ and determining the matching $i$
[notice that here $y=a\cdot g^i\bmod p$ ]
- if $i=r-1$ then exit the repeat loop
- $i\gets i+1$ and $X\gets a\cdot g$
- $z\gets g^r\bmod n$ (by modular exponentiation)
- $j\gets 0$ and $y\gets 1$
- repeat until $y$ (and it's matching $i$) is found in the table
- $j\gets j+1$ and $y\gets y\cdot z\bmod p$
- $x\gets j\cdot r-i\bmod|g|$
- output "the smallest non-negative integer solution is " $x$, and stop.
The first repeat loop advances by "baby steps" of one additional power of $g$. The second repeat loop advances by "giant steps" of $r$ additional powers of $g$. The algorithm works because when there's a match, $g^{j\cdot r}\bmod p=a\cdot g^i\bmod p$.
Assuming we know that $p$ is prime, and the order $|g|$, this algorithm has time complexity $\mathcal O(\sqrt{|g|}\cdot\log^2p+\log^3p)$ with $|g|<p$, for standard algorithms. That's a great improvement over search by enumeration thanks to replacing $|g|$ by $\sqrt{|g|}$. However the space complexity is $\mathcal O(\sqrt{|g|}\cdot\log p)$, and that makes it impractical for parameters of cryptographic interest.
Pollard's rho for discrete logarithm
The space complexity of baby-step/giant-step can be reduced down to the point of becoming a non-issue, by using collision search rather than a table. See wikipedia's Pollard's rho for the discrete logarithm. The time complexity remains similar to that in baby-step/giant-step.
For a more detailed analysis of the technique, and how it can be used to distribute the work over multiple CPUs, see Paul C. van Oorschot & Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications, in JoC 1999.
That parallel version of Pollard's rho for discrete logarithm is the algorithm of choice in many cases of cryptographic interest, including Diffie-Hellman when the order $|g|$ is moderate (say up to 50 decimal digits) and $p$ is much larger. And also when, instead of multiplication modulo $p$, it's used another group operation, as is the case in Elliptic Curve Cryptography.
Even better algorithms
In the case of multiplication modulo $p$, and when $|g|$ is not particularly small, there are even better algorithms: Index calculus, and the function field sieve.
Parallel variants of the later have been used for $p$ of up to 240 decimal digits, and $|g|$ not particularly small.
† Such sizes of $p$ and $|g|$ was borderline safe in the 1990s, and no longer is safe. Nowadays (2022), for new applications, 2048-bit or 3072-bit $p$ (617 or 925 decimal digits) and at least 256-bit $|g|$ (≈77 decimal digits) are customary, in order to resist both the function field sieve and parallel Pollard's rho.