# What Is The Maximum Value For N In Discrete Logarithm Problems?

I have some code, which can crack a discrete logarithm problem in ~ O(0.5n) time. However, this only works if, in the following, N is less than P:

G^N (mod P). To be clear, my program can figure out the value of N based on G and P as long as N is in between 1 and P (inclusive and exclusive respectively).

This would be helpful for cracking something like Diffie-Hellman, but I have one question: In most discrete logarithm problems like this one, is it common practice to only choose values of N between 1 and P?

Also, I'm not sure if this is the right forum for this kind of thing, please inform me if it is not.

• If a solution exists, there must exist another solution satisfying your constraints, because $G^N \equiv G^{ N \mod{P-1}} \pmod{P}$ (I am assuming $P$ is prime here). In other words, adding or subtracting $P-1$ in the exponent does not change anything. Nov 21 at 18:53
• How $n$ is related to $N$? Nov 21 at 18:53
• n is just P - 1, because in my algorithm, the number of steps it takes to complete increases relative to the size of P - 1. Nov 21 at 20:25

The problem of solving for $$N$$ the equation $$G^N\equiv A\pmod P$$ for given integers $$P$$, $$G$$, $$A$$ is generally stated for integer $$N$$ with $$0 for some $$Q.

The function $$N\mapsto G^N\bmod P$$ is periodic. Hence if $$N$$ is a solution, the set of all solutions is obtained by adding a multiple of the period¹ of that function to that $$N$$. Thus it's pointless to consider $$N$$ larger than the period if we can find it, in which case we choose the upper limit for $$P$$ equal to that period, and name it $$Q$$. In any case, since $$G^N\bmod P$$ (when not $$0$$) belongs to the integers in $$[1,P-1]$$, which has $$P-1$$ elements, the period cant exceed $$P-1$$, hence $$Q.

That period $$Q$$ is the order of $$G$$ modulo $$P$$, that is the smallest integer $$Q$$ with $$G^Q\equiv1\pmod P$$. It depends on $$G$$. It is a divisor of $$\lambda(P)$$, where $$\lambda$$ is Carmichael's function. $$\lambda(P)$$ is $$P-1$$ when $$P$$ is prime, lower otherwise.

When the factorization of $$P$$ is known (including prime $$P$$), $$\lambda(P)$$ is easy to compute, and the order of $$G$$, being a divisor of $$\lambda(P)$$, also is easy to compute.

Standard practice in cryptography are $$P$$ a large prime (e.g. at least 1024-bit, that is 309 decimal digits), and $$Q$$ the order of $$G$$ modulo $$P$$, thus $$Q$$ a divisor of $$P-1$$. Depending on cryptosystem that can be $$Q=P-1$$, or prime $$Q=(P-1)/2$$, or a mildly large prime $$Q$$ (e.g. at least 160-bit, that is 49 decimal digits) dividing $$P-1$$. The former two are common in Diffie-Hellman, the later in Schnorr signature and DSA.

Depending on the magnitude of $$P$$ and $$Q$$, the best algorithms we know to find $$N$$ are either

• Pollard's rho, which cost is $$\mathcal O(\sqrt Q)$$ modular multiplications modulo $$P$$.
• index calculus, which cost grows sizably slower when $$\log (Q)\lesssim\log(P)$$.

¹ We define the period as the lowest strictly positive period.

• Thank you. This helped a lot. Nov 21 at 20:27