解答つき整数論と合同式ワークシート

無料で印刷できる整数論と合同式のワークシート：やさしい問題から試験レベルまで 6 問、解答つき。印刷するか PDF で保存できます。

新しいワークシートヒントつきでオンライン練習

先生方へ： 授業で自由に印刷・コピーしてお使いいただけます。新しいワークシートごとに数値が変わり、専用の解答が付きます。授業ページに ExamProblems へのリンクを載せていただけると嬉しいです。

名前: ____________________   日付: ____________

1.やさしい

大きな数をそのまま掛け算せずに (903·894 + 63) mod 8 を求めましょう：まず簡約します。

n = 8
(903·894 + 63) mod 8 =
2.やさしい
aqbr544=?·323+??=?·?+??=?·?+??=?·?+?

最小公倍数 lcm(544, 323) を求めてください。まずユークリッドの互除法で gcd を求めましょう。

a = 544b = 323
lcm(544, 323) =
3.ふつう

オイラーのトーシェント関数 φ(200)、つまり 1 から 200 までの整数のうち 200 と互いに素なものの個数を求めてください。

n = 200 = 23·52
φ(200) =
4.ふつう

67 を法とする 31 の逆元を求めてください：0 < x < 67 かつ 31·x ≡ 1 (mod 67) を満たす数 x です。

a = 31n = 67
31−1 mod 67 =
5.むずかしい
mc = me​ mod ncm = cd​ mod nm(n, e) = (799, 5)d = ?

ある RSA 鍵は、素数 p = 17 と q = 47、公開指数 e = 5 を使います。秘密指数 d（0 < d < φ(n)）を求めてください。

p = 17q = 47e = 5
d =
6.むずかしい
73c = me​ mod n?m = cd​ mod nm(n, e) = (731, 5)d

メッセージ m = 73 を RSA 公開鍵 (n, e) = (731, 5) で暗号化してください。暗号文 c を求めてください。

n = 731e = 5m = 73
c =

解答

  1. 1. (903·894 + 63) mod 8 = 1
  2. 2. lcm(544, 323) = 10336
  3. 3. φ(200) = 80
  4. 4. 31−1 mod 67 = 13
  5. 5. d = 589
  6. 6. c = 184

ステップごとの詳しい解答：このトピックは examproblems.com で練習できます。