Harekaze Advent Calendar 2017 day3

あどべ3日目です

adventar.org

機関室の幽霊と化した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に実装したテストを通過する状態を保ちながらゴルフしました．（関数名の変更に伴ったテストの書き換えはしていますが，それ以外は変更していません）テストはカーマイケル数とランダムに生成した数について試し割りと結果を比較しています．