數論 - UVA 10006 - Carmichael Number
UVa 10006 Carmichael Number
問題
密碼學（cryptography）是電腦科學中一個重要的領域，密碼學的演算法常會用到大的質數。然而，要檢查一個大數是否是質數並不是那麼容易。一個窮舉的方法就是檢查所有小於等於其根號的數是否可以被整除。但是這方法所花費的時間及空間還是相當多。然而有一些機率的測試可以低花費得到高可信度。費馬測試（Fermat test）就是其中之一。
令 a 是一個介於 2 到 n-1 的數（在這裡 n 是我們要檢查是否為質數的數），那麼n可能是一個質數，如果以下的式子成立的話：
如果一個數通過費馬測試許多次，那麼他是質數的機率就很高。不幸的是，有些數不是質數但仍然能通過所有的費馬測試。我們稱這些數為Carmichael numbers。
你的任務就是寫一個程式來檢驗一個數是否是Carmichael number。
* 中文翻譯：Lucky 貓
Input
每組測試資料一列，含有一個整數 n（2 < n < 65000）。n=0代表輸入結束。
Output
對每一組測試資料，輸出其是否為Carmichael number。
Sample Input
1729
17
561
1109
431
0
Sample Output
The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.
解法
github
先判斷是否是質數, 再利用 UVa 374 Big mod 的技巧, 來加速計算 a ^ n mod n
a^2 mod m = a * a mod m = ((a mod m) * (a mod m) ) mod m
問題
密碼學（cryptography）是電腦科學中一個重要的領域，密碼學的演算法常會用到大的質數。然而，要檢查一個大數是否是質數並不是那麼容易。一個窮舉的方法就是檢查所有小於等於其根號的數是否可以被整除。但是這方法所花費的時間及空間還是相當多。然而有一些機率的測試可以低花費得到高可信度。費馬測試（Fermat test）就是其中之一。
令 a 是一個介於 2 到 n-1 的數（在這裡 n 是我們要檢查是否為質數的數），那麼n可能是一個質數，如果以下的式子成立的話：
an mod n = a
你的任務就是寫一個程式來檢驗一個數是否是Carmichael number。
* 中文翻譯：Lucky 貓
Input
每組測試資料一列，含有一個整數 n（2 < n < 65000）。n=0代表輸入結束。
Output
對每一組測試資料，輸出其是否為Carmichael number。
Sample Input
1729
17
561
1109
431
0
Sample Output
The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.
解法
github
先判斷是否是質數, 再利用 UVa 374 Big mod 的技巧, 來加速計算 a ^ n mod n
a^2 mod m = a * a mod m = ((a mod m) * (a mod m) ) mod m
留言
張貼留言