# discrete logarithm

Let $p$ be a prime. We know that the group $G:=(\mathbb{Z}/p\mathbb{Z})^{*}$ is cyclic. Let $g$ be a primitive root of $G$, i.e. $G=\{1,g,g^{2},\dots,g^{p-2}\}$. For a number $x\in G$ we want to know the unique number $0\leq n\leq p-2$ with

 $x=g^{n}.$

This number $n$ is called the or index of $x$ to the basis $g$ and is denoted as $\operatorname{ind}_{g}(x)$. For $x,y\in G$ it satisfies the following properties:

 $\displaystyle\operatorname{ind}_{g}(xy)$ $\displaystyle=\operatorname{ind}_{g}(x)+\operatorname{ind}_{g}(y);$ $\displaystyle\operatorname{ind}_{g}(x^{-1})$ $\displaystyle=-\operatorname{ind}_{g}(x);$ $\displaystyle\operatorname{ind}_{g}(x^{k})$ $\displaystyle=k\cdot\operatorname{ind}_{g}(x).$

Furthermore, for a pair $g,h$ of distinct primitive roots, we also have, for any $x\in G$:

 $\displaystyle\operatorname{ind}_{h}(x)$ $\displaystyle=\operatorname{ind}_{h}(g)\cdot\operatorname{ind}_{g}(x);$ $\displaystyle 1$ $\displaystyle=\operatorname{ind}_{g}(h)\cdot\operatorname{ind}_{h}(g);$ $\displaystyle\operatorname{ind}_{g}(-1)$ $\displaystyle=\frac{p-1}{2}.$

It is a difficult problem to compute the discrete logarithm, while powering is very easy. Therefore this is of some interest to cryptography.

Title discrete logarithm DiscreteLogarithm 2013-03-22 14:54:27 2013-03-22 14:54:27 mathwizard (128) mathwizard (128) 7 mathwizard (128) Definition msc 11A15 index
{"ft_lang_label":"__label__en","ft_lang_prob":0.83973694,"math_prob":0.9999081,"size":819,"snap":"2020-10-2020-16","text_gpt3_token_len":213,"char_repetition_ratio":0.121472396,"word_repetition_ratio":0.0,"special_character_ratio":0.2735043,"punctuation_ratio":0.12179487,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99998593,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-03-29T05:48:42Z\",\"WARC-Record-ID\":\"<urn:uuid:4f6d10a5-61ea-4908-950d-1ed3a82e993a>\",\"Content-Length\":\"15111\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:df22f1fc-054c-4220-bb0c-ffe4f60a22e1>\",\"WARC-Concurrent-To\":\"<urn:uuid:1ef20c2f-3e83-412f-82fe-611011678304>\",\"WARC-IP-Address\":\"129.97.206.129\",\"WARC-Target-URI\":\"https://planetmath.org/discretelogarithm\",\"WARC-Payload-Digest\":\"sha1:KSLHQ7DLX3BAUTOXSS7EGEJL4SHKBDOA\",\"WARC-Block-Digest\":\"sha1:RN722EOBLB2GOF3UGEBA3GTZ4B4AHHVD\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-16/CC-MAIN-2020-16_segments_1585370493818.32_warc_CC-MAIN-20200329045008-20200329075008-00451.warc.gz\"}"}