推 subtropical :謝謝回答! 07/04 03:44
※ 引述《subtropical (風大雨大)》之銘言：
: ※ 引述《subtropical (風大雨大)》之銘言：
: : 1.是非題
: : 6 是 primitive root mod 7
: : 5 ""
: : 1 ""
: a.) 6 = (7-1)
: (7-1)^6 = 1 mod 7
: => 1^6 = 1 7
: b.) 5 = (7-2)
: (7-2)^5 = 1 mod 7
: => -2^5 = 1 mod 7
: => -32 = 1 mod 7 不成立
: 但是 5 25 125 625 3125 15625
: 5 4 6 2 3 1
: 5是promitive root mod 7 我是不是哪邊搞錯了@@"
乖乖的一個一個乘
說 6 = 7-1 這只是方便你算 6^k = (-1)^k (mod 7)
但是我們知道 φ(7) = 6, i.e. | Z_7^×| = 6
所以任何一個元素生成出來的乘法群大小都整除 6 (Lagrange's theorem)
假設對某個數 x, <x>≠Z_7^×
那麼 | Z_7^×|/| <x> | 必然有一個 | Z_7^×| 的質因數
6=2*3, 所以對任何元素你只要檢查 x^(6/2), x^(6/3) 不是 1, 那 x 就是生成元
: : 2.請找出解
: : x^3 = 4 (mod 11)
: 硬代發現5是一解
: 可是接下來x^3 - 4除上x-5卻無法整除
推文已經分解了 要記得這是 mod 11...
另外 解 x^a = b (mod p)
若已經找出一個生成元 g, 可以設 x = g^y, 接著求出 b = g^c
變成求解 g^(ay) = g^c (mod p)
這等同 ay = c (mod p-1) //因為 Z_p^×的大小是 p-1
求解 y 是容易的, 例如用 Extended Euclidean algorithm
(當然可能很多解)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.52.94