In Mathematics is there a discrete logarithm function?

391 Views Asked by At

enter image description here

I find it difficult to understand this part in this book.

Because, as far as I know, there is no unique function or formula for discrete logarithms. I cann't understand what this formula does. Is this formula to direct calculate the discrete logarithm? Or is there a direct unique formula or funtion that calculates special discrete logarithms?

1

There are 1 best solutions below

0
On

The definition of the discrete logarithm used there: if $g$ is a primitive root mod $p$ - that is, it generates the multiplicative group mod $p$ - and $u\not\equiv 0\mod p$ then $\log_g u$ is $\min\{L: g^L \equiv u\mod n, L\ge 0\}$. This is always an integer in $[0,p-2]$.

Now, what's with the formula? An integer in $[0,p-1]$ can be interpreted mod $p$, and the possible values are all distinct. Throw in an arbitrary value at zero, and this can be interpreted as a function from $\mathbb{Z}/p$ to itself. It shouldn't be, but it can. Every such function can be written as a polynomial function of degree at most $p-1$, and someone went to the trouble of figuring out what that is in this case. The arbitrary value assigned to zero in this case, by the way, is $0$ if $p=2$ and $-1$ if $p$ is odd.