離散對數/循環組範例的問題……誰能為我澄清這個概念？
我正在觀看這個關於離散對數範例的非常短的影片：https ://www.youtube.com/watch?v= SL7J8hPKEWY 並且在 0:38 他們顯示了所有可能的值，如果 $ p = 17 $ 和 $ g = 3 $ . 在 1:00，他們聲明解決方案同樣可能是 1 到 17 之間的任何整數。
我的問題是；
- 關於什麼 $ 0 $ ? 根據我對循環群的了解， $ 17 \bmod 17 $ 只是 $ 0 $ . 我想他們的意思是 $ 0 $ 和 $ 16 $ 那麼，但是……為什麼不是 $ 3^x = 0 \bmod 17 $ 在影片中顯示呢？
- 如果 $ 3 $ 實際上是 17 的原始根，也就是生成器，其值為 $ x $ 應該存在吧？還是我錯過了什麼？
- 如果 $ p = 17 $ , 組的順序不應該等於 $ 17 $ 也？他們缺少一個值 $ x $ 然後。
- 如果我是對的，價值是多少 $ x $ 在 $ 3^x = 0 \bmod 17 $ ?
您正在查看的組是乘法組模 $ 17 $ 其中的權力 $ 3 $ 產生。作為一個集合，對於一般 $ n $ 這不包括 $ 0 $ 並且通常寫為 $$ (\mathbb{Z}_n^\ast,\cdot) $$ 在哪裡 $ \mathbb{Z}_n^\ast \subseteq {1,2,\ldots,n-1} $ 對於任何正整數 $ n\geq 2. $
如果 $ n=p $ 是一個素數，那麼這個集合實際上是所有 $ {1,2,\ldots,p-1} $ 否則，它只是中的元素集 $ \mathbb{Z}_n $ 這是相對質數 $ n. $ 如果 $ n=p $ 一個素數，則該群也是循環的，這意味著單個元素 $ g $ 可以生成其所有成員作為權力 $ g^i\pmod p. $
對於你的例子 $ p=17, $ 和 $ g=3. $
**編輯：**如果 $ n $ 是非素數，比如說 $ n=pq $ 在哪裡 $ p\neq q $ 是素數，那麼有 $ n/p $ 中的元素 $ {0,1,\ldots, n-1} $ 可以被 $ p. $ 有 $ n/q $ 中的元素 $ {0,1,\ldots, n-1} $ 可以被 $ q $ . 由於零可以被兩者整除，我們得到 $$ n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right) $$ 相對質數的元素 $ n $ 這是乘法組的大小。
對於一般 $ n $ 我們有 $ \varphi(n) $ 組中的元素，其中 $ \varphi(\cdot) $ 是歐拉的常函式。