情報基礎数学 I ・構造数理 期末試験 (2006 年 7 月 28 日) 注意. 途中の計算や議論も書いて下さい. 途中の計算や議論がない場

合, 答えが合っていても減点もしくは零点になる場合があります.

1. 次の連立一次合同式を解け.

x ≡ 5 (mod 7)
x ≡ 4 (mod 11)
x ≡ 3 (mod 13)

2. 3^{185} を 37 で割ったときの余りを求めよ.

3. 次の問いに答えよ.

(1) R(11) ∈ ℤ/96ℤ = {R(0), R(1), …, R(95)} に対して, (R(11))^{−1} = R(a), 1 ≤ a ≤ 95

をみたす自然数 a を求めよ.

(2) ℤ/96ℤ = {R(0), R(1), …, R(95)} において, 次の等式をみたす整数 b (0 ≤ b ≤ 95) を求めよ. (次の式の演算は ℤ/96ℤ での演算である.)

R(b) = (R(73) − R(79)) ÷ R(11)

(3) 暗号化鍵 (公開鍵) が (n, e) = (119, 11) となる RSA 暗号について, 暗号文 y = 3 を解読せよ. (すなわち, 暗号化鍵から復号化鍵 d を求め, 暗号文 y を復号化し, 元の平文 x を求めよ.)

4. (a, 28) = (b, 28) = 1 となる整数 a, b に対して, a^{108} ≡ b^{60} (mod 28)

が成り立つことを示せ.

5. 一次合同式 91x ≡ 26 (mod 221) を解け. 更に, 221 を法としたときの解の個数を求めよ.

次の 6, 7 のうちのどちらか 1 問を解け.

6. φ(n) ≤ 3 となる自然数 n を全て求めよ.

7. p を奇素数とする. このとき, 条件

φ(n) = \frac{(p − 1)n}{2p}

をみたす自然数 n を求めよ.