作者mic2754 (都是假的)
看板Math
標題[代數]
時間Tue Jun 16 03:01:17 2020
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://webptt.com/m.aspx?n=bbs/Math/M.1592247679.A.068.html
1F：→ Ricestone : 1.不用算1~10次方，因為11是質數，子群order只會是 06/16 03:15
2F：→ Ricestone : 1或11，只要判斷8次方是不是1就好 06/16 03:15
3F：→ Ricestone : 而8次方的mod應該不難算吧，底隨時變小就好 06/16 03:20
4F：→ Ricestone : 第一行是指(8次方的)1~10次方，應該知道我的意思 06/16 03:26
5F：推 MisatoMitumi: 1155=3*5*7*11, 所以x^2=1 (mod1155)若且唯若 06/16 04:02
6F：→ MisatoMitumi: x^2=1 (mod 3, 5, 7, 11) 剩的就中國剩餘定理和排列 06/16 04:03
7F：→ MisatoMitumi: 組合 06/16 04:03
8F：→ mic2754 : 感謝兩位回答，第一題我懂了，第二題還是不大明白， 06/16 09:02
9F：→ mic2754 : 它套用中國剩餘定理不是只能解出x^2嗎？x還是不知道 06/16 09:02
10F：→ mic2754 : 有多少組x吧？ 06/16 09:02
11F：→ Ricestone : x= 1 or -1 mod p 06/16 09:07
12F：→ Ricestone : p=3,5,7,11 每組會解出一個x 06/16 09:08
有稍微get到一些，但還是沒有很懂，能麻煩再解釋一下嗎？感謝
※ 編輯: mic2754 (1.160.36.187 臺灣), 06/16/2020 09:30:25
13F：→ Ricestone : (1,1,1,1),(1,1,1,-1),...,(-1,-1,-1,-1)各只會解出 06/16 09:35
14F：→ Ricestone : 一個x 06/16 09:35
了解，所以答案是2^4=16種囉～
謝謝r大解釋
※ 編輯: mic2754 (1.160.36.187 臺灣), 06/16/2020 09:43:31
15F：推 Vulpix : 89是質數，Z_89*=Z_88。算完第一個3^8就知道3是gen. 06/16 10:30
16F：→ Vulpix : 所以3^2=9也是。至於6……就再檢查吧。 06/16 10:31
17F：推 Vulpix : 反正要檢查的四個數字的質因數只有2和3，所以先算 06/16 10:35
18F：→ Vulpix : 3^8=-25,2^8=-11就方便很多了。 06/16 10:35