[代數] 兩題有限體相關

看板Math作者 (都是假的)時間5年前 (2020/06/16 03:01), 5年前編輯推噓3(3推 0噓 15→)
留言18則, 4人參與, 5年前最新討論串1/1
http://i.imgur.com/bvyBVCe.jpg
如圖兩題 想法: 第一題是生成generator常見的操作。因為根據費馬小定理，每個選項11次方後再mod89都會是1，所以我的理解是去驗證各選項的1到10次方是否為1，若有為1的情況則表示該選項不是generator，這想法應該是沒錯的，但是如果要這樣一個一個檢查計算太繁瑣了 ，一開始就要先把數字做8次方，真的太難算了，所以上來請問有沒有什麼好方法。 第二題就真的幾乎沒什麼想法了……我只知道+-1絕對是其中兩解，1155不是質數所以1應該是存在其他平方根，但是我不太清楚具體上有幾組，除非窮舉，但是這太不實際了，所以一樣放上來請教。 麻煩各位高手了，謝謝。 ----- Sent from JPTT on my Samsung SM-G885Y. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.214.149.67 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1592247679.A.068.html
→
06/16 03:15, 5年前 , 1F
1.不用算1~10次方，因為11是質數，子群order只會是
06/16 03:15, 1F
→
06/16 03:15, 5年前 , 2F
1或11，只要判斷8次方是不是1就好
06/16 03:15, 2F
→
06/16 03:20, 5年前 , 3F
而8次方的mod應該不難算吧，底隨時變小就好
06/16 03:20, 3F
→
06/16 03:26, 5年前 , 4F
第一行是指(8次方的)1~10次方，應該知道我的意思
06/16 03:26, 4F
推
06/16 04:02, 5年前 , 5F
1155=3*5*7*11, 所以x^2=1 (mod1155)若且唯若
06/16 04:02, 5F
→
06/16 04:03, 5年前 , 6F
x^2=1 (mod 3, 5, 7, 11) 剩的就中國剩餘定理和排列
06/16 04:03, 6F
→
06/16 04:03, 5年前 , 7F
組合
06/16 04:03, 7F
→
06/16 09:02, 5年前 , 8F
感謝兩位回答，第一題我懂了，第二題還是不大明白，
06/16 09:02, 8F
→
06/16 09:02, 5年前 , 9F
它套用中國剩餘定理不是只能解出x^2嗎？x還是不知道
06/16 09:02, 9F
→
06/16 09:02, 5年前 , 10F
有多少組x吧？
06/16 09:02, 10F
→
06/16 09:07, 5年前 , 11F
x= 1 or -1 mod p
06/16 09:07, 11F
→
06/16 09:08, 5年前 , 12F
p=3,5,7,11 每組會解出一個x
06/16 09:08, 12F
有稍微get到一些，但還是沒有很懂，能麻煩再解釋一下嗎？感謝 ※ 編輯: mic2754 (1.160.36.187 臺灣), 06/16/2020 09:30:25
→
06/16 09:35, 5年前 , 13F
(1,1,1,1),(1,1,1,-1),...,(-1,-1,-1,-1)各只會解出
06/16 09:35, 13F
→
06/16 09:35, 5年前 , 14F
一個x
06/16 09:35, 14F
了解，所以答案是2^4=16種囉～ 謝謝r大解釋 ※ 編輯: mic2754 (1.160.36.187 臺灣), 06/16/2020 09:43:31
推
06/16 10:30, 5年前 , 15F
89是質數，Z_89*=Z_88。算完第一個3^8就知道3是gen.
06/16 10:30, 15F
→
06/16 10:31, 5年前 , 16F
所以3^2=9也是。至於6……就再檢查吧。
06/16 10:31, 16F
推
06/16 10:35, 5年前 , 17F
反正要檢查的四個數字的質因數只有2和3，所以先算
06/16 10:35, 17F
→
06/16 10:35, 5年前 , 18F
3^8=-25,2^8=-11就方便很多了。
06/16 10:35, 18F
‣ 更多 mic2754 的文章
文章代碼(AID): #1UvyL_1e (Math)