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

16.1

(a) 5¹³=5⁸⁺⁴⁺¹≡21 (mod 23)

(b) 28⁷⁴⁹=28^{512+128+64+32+8+4+1}≡289 (mod 1147)

16.2

(a)

k=Σ_i(2ⁱk_i) (0≤i≤[log₂ k], k_i=0,1)とする。

2ⁱk_i (k_i=1)の各項に対し、ステップ(4)(5)でaの冪が2倍になり、

kの値が半分になるので、iステップ後には、a²ⁱ (mod m)が取り出されて、

ステップ(3)でbに格納され、(5)でこの冪の項は捨てられる。

したがって、k_i=1の各iについて、iステップ後にa²ⁱ (mod m)が、

bに次々に掛けられていくことになるので、

これは繰り返し自乗法の計算プロセスと同じであり、

同じ全てのiについて実行が終了したときは、a^k (mod m)を得る。

(c) (i) 562 (ii) 3214 (i) 1296608

16.3

(a) 2938。素数でない。

(b) 1。素数かも知れないが、擬素数かも知れない。

16.5

3362。素数でない。