問題１.素数判定法
 Miller-Rabinテストにより、
n=24×5+1=81が素数か否か
確認する。空欄を埋めよ。
1. s=4, r=5, a=2, t=1とする
2. y0=(25 mod 81) = 32
3. y1=(y02 mod 81) =52
4. y2=(y12 mod 81) =31
5. y3=(y22 mod 81) = 70
 Miller-Rabinテスト
（入力）奇数n≧3、繰返し回数t
（出力）nが素数(prime)／合成数(composite)
（アルゴリズム）
n－1=2sr（rは奇数）と表し、i=0とする
prime Y
j=j+1
「81は素数である。」
正しければY、誤りであればNを
空欄に書け。
N
yj=y2j-1 mod n
Y
yj=n-1
N
N
j=s-1
Y
composite
i=t
N
i=i+1
a(1≦a≦n-1)を選択
y0=ar mod n
y0=1 or n-1
N
j=0
Y

復習テスト9

演習問題

復習テスト12