1.やさしい
大きな数をそのまま掛け算せずに 100² mod 7 を求めましょう：まず簡約します。
n = 7
100² mod 7 =
解答つき整数論と合同式ワークシート
2.やさしい
大きな数をそのまま掛け算せずに 500² mod 6 を求めましょう：まず簡約します。
n = 6
500² mod 6 =
3.ふつう
x ≡ 3 (mod 5) かつ x ≡ 2 (mod 7) を満たす最小の正の整数 x を求めてください。
x ≡ 3 (mod 5)x ≡ 2 (mod 7)
x =
4.ふつう
53 を法とする 21 の逆元を求めてください：0 < x < 53 かつ 21·x ≡ 1 (mod 53) を満たす数 x です。
a = 21n = 53
21−1 mod 53 =
5.むずかしい
ある RSA 鍵は、素数 p = 31 と q = 41、公開指数 e = 23 を使います。秘密指数 d（0 < d < φ(n)）を求めてください。
p = 31q = 41e = 23
d =
6.むずかしい
ある RSA 鍵は p = 43、q = 47、e = 13 を使います。暗号文 c = 812 を復号して、メッセージ m を求めてください。
p = 43q = 47e = 13c = 812
m =
解答
- 1. 100² mod 7 = 4
- 2. 500² mod 6 = 4
- 3. x = 23
- 4. 21−1 mod 53 = 48
- 5. d = 887
- 6. m = 182
ステップごとの詳しい解答：このトピックは examproblems.com で練習できます。