[파이썬 코드] 고속지수연산

 

 고속지수연산 알고리즘을 파이썬으로 구현한 코드입니다 :)

 

	# 이진수 변환
	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
	# 사용 - 11^22 mod 21 = 4
	print(fastExpOp(11,22,21))

view raw fastExpOp.py hosted with ❤ by GitHub

암호론, 인증시스템 수업을 들으면서 배운 개념으로, 큰 값을 이용해서 암호 키를 다루는 암호론에서 지수연산이 많은데 이때 이 지수연산을 빠르게 해결하기 위해 나온 방식이라고 한다.