シルヴァーマン 「はじめての数論」第3版 第22章練習問題

22.1

(a) x≡5 (mod 37)

(b) 解なし。

(c) x≡6 (mod 37)

(d) x≡10, 14, 23, 27 (mod 37)

22.2

(a)

a	1	2	3	4	5	6	7	8	9
I(a)	16	14	1	12	5	15	11	10	2
a	10	11	12	13	14	15	16
I(a)	3	7	13	4	9	6	8

(b) x≡7 (mod 17)

(c) x≡3, 14 (mod 17)

22.3

(a) I(a)+I(b) ≡0 (mod p-1)より、I(a)≡-I(b) (mod p-1)。

(b) a≡-b≡(p-1)b (mod p)より、I(a)≡I(p-1)+I(b) (mod p-1)。

ここで、奇素数pを法とした原始根gについてx=g^(p-1)/2とすると、x²=g^(p-1) ≡1(mod p)であり、

x≢1(mod p)だからx≡-1≡p-1(mod p)。よってI(p-1) ≡(p-1)/2 (mod p-1)となる。

したがって、I(a)≡(p-1)/2+I(b) (mod p-1)。

(c) 特に関係なさそう。

22.4

(a)

与えられた合同式の、ある原始根を底とした指数を取り、kI(x)≡0 (mod p-1)。

第8章定理8.1の一次合同式定理とk|p-1より、

この合同式は解I(x) (0≤ I(x) <p-1)をgcd(k,p-1)=k個もつ。

(b)

与えられた合同式の、ある原始根を底とした指数を取り、kI(x)≡I(a) (mod p-1)。

第8章定理8.1の一次合同式定理から、この合同式は

・I(a) ≢0 (mod gcd(k,p-1))なら解なし。

・I(a) ≡0 (mod gcd(k,p-1))なら解はgcd(k,p-1)個。

(c)

gcd(111, 1986)=3だからI(729)=6≡0 (mod 3)。したがって(b)から解は3個。

22.5

a	1	2	3	4	5	6	7	8	9	10
I(a)	46	18	20	36	1	38	32	8	40	19
a	11	12	13	14	15	16	17	18	19	20
I(a)	7	10	11	4	21	26	16	12	45	37
a	21	22	23	24	25	26	27	28	29	30
I(a)	6	25	5	28	2	29	14	22	35	39
a	31	32	33	34	35	36	37	38	39	40
I(a)	3	44	27	34	33	30	42	17	31	9
a	41	42	43	44	45	46
I(a)	15	24	13	43	41	23

22.6

(a)

v≡e₂(e₁^k)^-1=ma^rg^-rk≡ mg^rkg^-rk≡m (mod p)。

(b)

a≡g^k(mod p)を、公開されているa,g,pに対し解いてkを得れば、

アリスと同様に復号できる。

22.7

(a) (e₁, e₂)=(119537, 133768)

(b) 違う。例えばr=129383に対し(e₁, e₂)=(92787, 105745)

(c)  TOPSECRET