# Does the discrete log assumption hold if k > p

In discrete log cryptosystems like ElGamal it is noted that the "private key" $$k$$ should be chosen as any element of the group $$G$$ i.e. $$k < p-1$$. Does the integrity of the cryptosystem rely on $$k$$ being an element of the group or can it be larger as well (always assuming that $$g^k \bmod{p}$$ will be published in the public key)? If yes, can it be any arbitrarily selected number larger than the group?

• If $k>p-1$ then it is functionally and security-wise fully equivalent to $k\bmod (p-1)$ – SEJPM Oct 12 '19 at 17:00

Assume that you have chosen a large $$k > p$$, then one can show that $$k'$$ with

$$k = \ell \cdot (p-1)+ k'$$ can also be your equivalent key.

From Euler's Totient Theorem, we know that $$a^{\phi(n)} \equiv 1 \bmod n$$ for all $$a$$ relatively prime to $$n$$.

If your key $$k> p-1$$ then we can write it like below with division algorithm - division by $$p-1$$;

$$k = \ell\cdot (p-1)+ k' = \ell \cdot \phi(n)+ k'$$ Now place this into $$a$$'s power and use the Euler's Toitent Theorem:

$$a^k \equiv a^{\ell \cdot \phi(n)+ k'} \equiv a^{\ell \cdot \phi(n)} a^{k'} \equiv \underbrace{a^{(\phi(n))\ell}}_{\equiv 1 \bmod p} a^{k'} \equiv a^{k'} \bmod p$$

Therefore we have

$$a^{k'} \equiv a^k \bmod p$$ and by using $$k$$ you will not achieve any higher security, contrary you will calculate unnecessarily steps in modular powering.

If you want to achieve more security, you should use a larger modulus.