回分類題庫
d046: 6.原根
關鍵字: 100年台中區複賽

測資點 : 6 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 77 Times / 71 Users | Submit : 135 Times / 72 Users | Accepted rate : 99%
題目加入時間 : 2012-07-06 14:44

Content: 简体中文

離散對數(discrete logarithm)中,令 p>3 為質數,給定一整數 g, 0 < g < p-1,與整數 x,0 <= x <= p-1,若考慮對於不同的 x 值,所有 gx mod p 所產生的數所成的集合中包含不同的數若有 k 個,則稱整數 g 的序(order)為 k。若 k=p-1 則 g 稱為 mod p 之原根(primitive root)。

假設 p=11 ,g=2 ,0 <= x <= 10,則
20 mod 11 = 1, 21 mod 11 = 2, 22 mod 11 = 4, 23 mod 11 = 8, 24 mod 11 = 5,
25 mod 11 =10, 26 mod 11 =9, 27 mod 11 =7, 28 mod 11 = 3, 29 mod 11 = 6,
210 mod 11 = 1,
亦即:{20 mod 11, 21 mod 11, …, 210 mod 11}={1, 2, 4, 8, 5, 10, 9, 7, 3, 6}共10個, g=2之序為10。故g=2時為mod p之原根。

若p=11 ,g=3 ,0 <= x <= 10,則
30 mod 11 =1, 31 mod 11 =3, 32 mod 11 =9, 33 mod 11 =5, 34 mod 11 =4,
35 mod 11 =1, 36 mod 11 =3, 37 mod 11 =9, 38 mod 11 =5, 39 mod 11 =4,
310 mod 11 =1,
亦即:{30 mod 11, 31 mod 11, …, 310 mod 11}={1, 3, 9, 5, 4}共5個, g=3之序為5。故g=3時不為mod p之原根。

若p=11 ,g=4 ,0 <= x <= 10,則
40 mod 11 =1, 41 mod 11 =4, 42 mod 11 =5, 43 mod 11 =9, 44 mod 11 =3,
45 mod 11 =1, 46 mod 11 =4, 47 mod 11 =5, 48 mod 11 =9, 49 mod 11 =3,
410 mod 11 =1,
亦即:{40 mod 11, 41 mod 11, …, 410 mod 11}={1, 3, 9, 5, 4}共5個, g=4之序為5。故g=4時不為mod p之原根。

若p=11 ,g=6 ,0 <= x <= 10,則
60 mod 11 =1, 61 mod 11 =6, 62 mod 11 =3, 63 mod 11 =7, 64 mod 11 =9,
65 mod 11 =10, 66 mod 11 =5, 67 mod 11 =8, 68 mod 11 =4, 69 mod 11 =2,
610 mod 11 =1,
亦即:{60 mod 11, 61 mod 11, …, 610 mod 11}={1, 6, 3, 7, 9, 10, 5, 8, 4, 2}共10個, g=6之序為10。故g=6時為mod p之原根。

反覆此運算,可以發現當 g 為 2, 6, 7, 8 時,其序(order)為 10,故為 p=11 之原根,共有 4 個。

設計一個程式,輸入一個大於 3 的質數 p,找出所有比 p 小且為 mod p 之原根的數與個數。

Input:

由鍵盤輸入一個大於 3 的質數 p。

Output:

第一列請輸出所有比p小且為mod p之原根的數,
第二列請輸出第一列的個數。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
11

輸入2:
31

輸入3:
19

Sample Output :

輸出1:
2 6 7 8
4

輸出2:
3 11 12 13 17 21 22 24
8

輸出3:
2 3 10 13 14 15
6

Hint :

Author :

100年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum