[파이썬 코드] 오일러 판정

다음은 오일러 판정을 통해 2차잉여(QR) / 2차 비잉여(NQR)을 판정해주는 코드이다.

 

	def binary(val):
	b = []
	while val > 0:
	if val % 2 == 1:
	b.append(1)
	else:
	b.append(0)
	val = val // 2
	return b
	# 고속지수연산
	def fastExpOp(a, exp, n):
	# a : 밑, exp : 지수, n : 모듈러 값
	x = binary(exp)
	y = 1
	for i, xi in enumerate(x):
	if xi == 1:
	y = (a * y) % n
	a = (a*a) % n
	return y
	# 오일러 판정
	def eulerCriterion(z):
	exp = (z - 1) / 2
	qr = []
	qnr = []
	for i in range(1, z):
	if fastExpOp(i, exp, z) == 1:
	qr.append(i)
	else:
	qnr.append(i)
	print('2차 잉여(QR)', qr)
	print('2차 비잉여(QNR)', qnr)
	eulerCriterion(21)

view raw eulerCriterion.py hosted with ❤ by GitHub

Z(21)*에 대해 QR, NQR은 다음과 같다.