1.やさしい
ユークリッドの互除法を使って gcd(343, 266) を求めてください。
a = 343b = 266
gcd(343, 266) =
解答つき整数論と合同式ワークシート
2.やさしい
大きな数をそのまま掛け算せずに 743² mod 9 を求めましょう：まず簡約します。
n = 9
743² mod 9 =
3.ふつう
オイラーのトーシェント関数 φ(1573)、つまり 1 から 1573 までの整数のうち 1573 と互いに素なものの個数を求めてください。
n = 1573 = 112·13
φ(1573) =
4.ふつう
オイラーのトーシェント関数 φ(143)、つまり 1 から 143 までの整数のうち 143 と互いに素なものの個数を求めてください。
n = 143 = 11·13
φ(143) =
5.むずかしい
ある RSA 鍵は p = 13、q = 19、e = 23 を使います。暗号文 c = 200 を復号して、メッセージ m を求めてください。
p = 13q = 19e = 23c = 200
m =
6.むずかしい
ある RSA 鍵は p = 5、q = 43、e = 23 を使います。暗号文 c = 142 を復号して、メッセージ m を求めてください。
p = 5q = 43e = 23c = 142
m =
解答
- 1. gcd(343, 266) = 7
- 2. 743² mod 9 = 7
- 3. φ(1573) = 1320
- 4. φ(143) = 120
- 5. m = 242
- 6. m = 23
ステップごとの詳しい解答：このトピックは examproblems.com で練習できます。