1.やさしい
ユークリッドの互除法を使って gcd(507, 130) を求めてください。
a = 507b = 130
gcd(507, 130) =
解答つき整数論と合同式ワークシート
2.やさしい
ユークリッドの互除法を使って gcd(570, 255) を求めてください。
a = 570b = 255
gcd(570, 255) =
3.ふつう
オイラーのトーシェント関数 φ(40)、つまり 1 から 40 までの整数のうち 40 と互いに素なものの個数を求めてください。
n = 40 = 23·5
φ(40) =
4.ふつう
オイラーのトーシェント関数 φ(13)、つまり 1 から 13 までの整数のうち 13 と互いに素なものの個数を求めてください。
n = 13 = 13
φ(13) =
5.むずかしい
メッセージ m = 1133 を RSA 公開鍵 (n, e) = (1517, 19) で暗号化してください。暗号文 c を求めてください。
n = 1517e = 19m = 1133
c =
6.むずかしい
ある RSA 鍵は、素数 p = 13 と q = 17、公開指数 e = 5 を使います。秘密指数 d（0 < d < φ(n)）を求めてください。
p = 13q = 17e = 5
d =
解答
- 1. gcd(507, 130) = 13
- 2. gcd(570, 255) = 15
- 3. φ(40) = 16
- 4. φ(13) = 12
- 5. c = 421
- 6. d = 77
ステップごとの詳しい解答：このトピックは examproblems.com で練習できます。