Harekaze Advent Calendar 2017 day3
あどべ3日目です
機関室の幽霊と化したTeam:Harekazeの黒木洋美です.最近CTFに参加しておらず申し訳ないということで,アドベントカレンダー書こうとしたんですがネタが無いのでコードを書きました.
Miller-Rabinの素数判定アルゴリズム(167バイト,python3)です.バグってない保証はありませんが使いたい方はお使いください.
import random as r def M(n,s): m,f=n-1,0 while s: o=m&-m;y=pow(r.randint(1,m),m//o,n);s-=1 while o:x,y=y,y*y%n;o//=2;f|=(y==1)*(x-1)*(x-m) f|=x-1 return f==0
CLRSの整数論的アルゴリズムの章の疑似コードを元に実装しています.CLRSの鈍器版を買うと精選トピックスとして整数論的アルゴリズムの章を読むことができます.さすが世界標準MIT教科書ですね(は?
ゴルフ前の実装はこちら.
import random, math def ModularExponentiation(x,p,n) : return pow(x,p,n) def MillerRabin(n,s): for j in range(0,s) : a = random.randint(1,n-1) if Witness(a,n) : return False return True def Witness(a,n) : u = (n-1)//((n-1)&-(n-1)) t = 0 tmp=((n-1)&-(n-1))//2 while tmp : t += 1 tmp //= 2 x = [ModularExponentiation(a,u,n)] for i in range(0,t) : x.append(x[-1]*x[-1]%n) if x[-1] == 1 and x[-2] != 1 and x[-2] != n-1 : return True if x[t] != 1 : return True return False def test() : def Naive(n) : i = 2 while i*i <= n : if n % i == 0 : return False i += 1 return True # OEIS-A002997 Carmichael = [561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973,75361,101101,115921,126217,162401,172081,188461,252601,278545,294409,314821,334153,340561,399001,410041,449065,488881,512461] for n in Carmichael : assert(MillerRabin(n,100) == Naive(n)) # random Random = [random.randint(1<<1,1<<32) for i in range(100)] for n in Random : print(n, Naive(n)) assert(MillerRabin(n,100) == Naive(n)) if __name__ == '__main__' : test()
関数testに実装したテストを通過する状態を保ちながらゴルフしました.(関数名の変更に伴ったテストの書き換えはしていますが,それ以外は変更していません)テストはカーマイケル数とランダムに生成した数について試し割りと結果を比較しています.