1.やさしい
ユークリッドの互除法を使って gcd(552, 300) を求めてください。
a = 552b = 300
gcd(552, 300) =
解答つき整数論と合同式ワークシート
2.やさしい
ユークリッドの互除法を使って gcd(180, 164) を求めてください。
a = 180b = 164
gcd(180, 164) =
3.ふつう
29 を法とする 18 の逆元を求めてください：0 < x < 29 かつ 18·x ≡ 1 (mod 29) を満たす数 x です。
a = 18n = 29
18−1 mod 29 =
4.ふつう
オイラーのトーシェント関数 φ(125)、つまり 1 から 125 までの整数のうち 125 と互いに素なものの個数を求めてください。
n = 125 = 53
φ(125) =
5.むずかしい
ある RSA 鍵は、素数 p = 19 と q = 43、公開指数 e = 5 を使います。秘密指数 d（0 < d < φ(n)）を求めてください。
p = 19q = 43e = 5
d =
6.むずかしい
ある RSA 鍵は、素数 p = 17 と q = 37、公開指数 e = 13 を使います。秘密指数 d（0 < d < φ(n)）を求めてください。
p = 17q = 37e = 13
d =
解答
- 1. gcd(552, 300) = 12
- 2. gcd(180, 164) = 4
- 3. 18−1 mod 29 = 21
- 4. φ(125) = 100
- 5. d = 605
- 6. d = 133
ステップごとの詳しい解答：このトピックは examproblems.com で練習できます。