DLP - formulae for length of $G_{list}$ in terms of prime $p$ for $g=2,3,...$

Question

The DLP is defined as: $$g^x \cong h \pmod{p}$$

Using $g=2$ and $g=3$ I've found that the size of list of unique $h$ values (I call the $G_{list}$) for primes from $p=3$ upto $p=19$ are of the form below;

$g = 2$;

1. $len(G_{list})=p-1$ for $p=3,5,11,13,19$
2. $len(G_{list})=\frac{p-1}{2}$ for $p=7,17$

$g = 3$;

1. $len(G_{list})=p-1$ for $p=5,7,17,19$
2. $len(G_{list})=\frac{p-1}{2}$ for $p=11$
3. $len(G_{list})=\frac{p-1}{4}$ for $p=13$

Question is why do these patterns emerge? Why do they seem to follow the formulae stated above?

I suspect this may be due to the properties of each congruence class of $Z_p$ under multiplication. I have done a quick Google search, and read Wikipedia's page on DLP, but could not see a relevant answer there for my question.

Answer 1

Fermat noted in his little theorem, that any non-multiple of prime $p$, $a$ raised to the exponent $p-1$ gives the same remainder as 1, on division by $p$. Namely 1.

Euler, then realized this lead to a factorization, where one factor was a multiple of $p$. The factorization was as follows: $$(a^{p-1\over 2}-1)(a^{p-1\over 2}+1)=pm$$ Unless $p=2$, this leads to exactly 1 of these factors divisible by $p$ . If $a$ is a quadratic residue, the first of these is a residue raised to the exponent $p-1$; the base necessarily not a multiple of $p$, and then subtracting 1. This yields, a multiple of $p$ for the first factor. The second yields a multiple, when the base is not a quadratic residue.

The Carmicheal function, is a result on the lowest exponent for which this works. I don't know it, though.

Here's how I figure the logic would go:

• $p-1$ if not a quadratic residue
• $p-1\over 2$ if a quadratic residue ( square mod p) , but not a fourth power ( square of a square mod p)
• etc.

It in no way helps with large DLP though. these values are also large.

A quicker ( not quick though) start would be to use the definition of congruence: $$y\equiv b\bmod m \iff y=mz+b$$ all variables integer.

Then you get to mod this by small primes to increase the result to test. But, as stated this is still slow. if not impractical.