(정수론/파이썬) 연속제곱법
# 연속제곱법
# '친절한 수론 길라잡이' 16장 연습문제 16.2
# 1. k를 2의 거듭제곱의 합으로 표현한다. 2진수로 표현
# 2. 연속제곱법을 이용하여 법 m에 대해 a의 거듭제곱을 계산하여 표를 만든다
# 3. A0*A1*A2*...*Ar (mod m)을 구한다.
from number_util import *
import math
def successiveSquaring(a, k, m):
expo = [] # 지수 보관 예: [1, 2, 4, 8, 16, 32, 64, 128, 256]
c = [] # 계수 보관 예: [1, 1, 1, 0, 0, 0, 1, 0, 1]
count = int(math.log2(k)) + 1 # 2의 거듭제곱값 중에서 k값을 넘지 않는 마지막 수까지의 갯수
for n in range(0, count + 1):
if 2**n > k:
break
expo.append(2**n)
print(expo)
# [1, 2, 4, 8, 16, 32, 64, 128, 256]
length = len(expo) # 9
bin_str = bin(k) # 0b101000111
bin_str = bin_str[2:] # 얖의 이진수 표시문자 '0b'를 제거. '0b101000111' -> '101000111'
bin_len = len(bin_str) # 9
if length != bin_len:
print("2진수 개수와 지수 개수가 다릅니다.")
print(f"count = {length}, bin_len = {bin_len}")
c = [0] * bin_len # 계수를 저장할 리스트 초기화 # [0, 0, 0, 0, 0, 0, 0, 0, 0]
for i in range(bin_len): # 0 ~ 8
# bin_str의 값들을 뒤집어 정수로 변환해서 c에 저장하기
# 뒤집는 이유는 지수 순서와 일치시켜 주기 위해
c[bin_len-1-i] = int(bin_str[i])
print(c) # [1, 1, 1, 0, 0, 0, 1, 0, 1]
# c와 expo의 원소들을 한 쌍씩 곱한 다음, 차례로 더하면 k의 값이 나와야 한다. 점검.
total = 0
for i in range(bin_len):
total += c[i] * expo[i]
print(total) # 327
if total != k:
print("계수와 2의 거듭제곱을 곱해서 모두 더했는데 k의 값과 다릅니다.")
mod_ks = []
# (mod k)를 했을 때 나온 값들(=나머지)을 저장.
# 예에서는 [7, 49, 695, 227, 349, 675, 123, 628, 298]
mod_k = a % m # 첫번째 원소로 '7 % m' 을 저장
mod_ks.append(mod_k)
for i in range(length - 1): # 총 8회만 mod_k 계산하면 됨
mod_k = mod_k ** 2 % m
mod_ks.append(mod_k)
print(mod_ks) # [7, 49, 695, 227, 349, 675, 123, 628, 298]
values = []
# 반환할 값들을 계산한다
for i in range(length): # 0~8
if c[i]: # 계수가 0이 아닌 (즉 1인) 지수의 mod_k만 뽑아낸다.
values.append(mod_ks[i])
print(values) # [7, 49, 695, 123, 298]
# 이 값들을 모두 곱해서 (mod m)을 해주면 원하는 값이 나온다.
val_len = len(values) # 5
# 총 val_len - 1 회만큼 계산한다. 한꺼번에 전부 곱하면 숫자가 너무 커질 수 있기 때문에
# 차례로 둘씩 곱하면서 (mod m)을 해준다.
res = values[0]
for i in range(1, val_len):
print(res, values[i])
res = res * values[i] % m
return res # 최종 값: a^k (mod m)
# 연속제곱법, 향상된 버전
# '친절한 수론 길라잡이 연습문제 16.2.b에 나온 코드
def successiveSquaring2(a, k, m):
b = 1
while k >= 1:
if k % 2 == 1:
b = a*b % m
a = a**2 % m
k = k // 2
return b # a^k (mod m)
a, k, m = 7, 327, 853 # 286
print("------", successiveSquaring(a, k, m))
print("******", successiveSquaring2(a, k, m))
a, k, m = 5, 13, 23 # 21
print("------", successiveSquaring(a, k, m))
print("******", successiveSquaring2(a, k, m))
a, k, m = 28, 749, 1147 # 289
print("------", successiveSquaring(a, k, m))
print("******", successiveSquaring2(a, k, m))
a, k, m = 2, 1000, 2379 # 562
print("------", successiveSquaring(a, k, m))
print("******", successiveSquaring2(a, k, m))
a, k, m = 567, 1234, 4321 # 3214
print("------", successiveSquaring(a, k, m))
print("******", successiveSquaring2(a, k, m))
a, k, m = 47, 258008, 1315171 # 1296608
print("------", successiveSquaring(a, k, m))
print("******", successiveSquaring2(a, k, m))
a, k, m = 7, 7386, 7387 # 702
print("------", successiveSquaring(a, k, m))
print("******", successiveSquaring2(a, k, m))
a, k, m = 7, 7392, 7393 # 1
print("------", successiveSquaring(a, k, m))
print("******", successiveSquaring2(a, k, m))
a, k, m = 2, 9990, 9991 # 3362
print("------", successiveSquaring(a, k, m))
print("******", successiveSquaring2(a, k, m))출력:
[1, 2, 4, 8, 16, 32, 64, 128, 256]
[1, 1, 1, 0, 0, 0, 1, 0, 1]
327
[7, 49, 695, 227, 349, 675, 123, 628, 298]
[7, 49, 695, 123, 298]
7 49
343 695
398 123
333 298
------ 286
****** 286
[1, 2, 4, 8]
[1, 0, 1, 1]
13
[5, 2, 4, 16]
[5, 4, 16]
5 4
20 16
------ 21
****** 21
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
[1, 0, 1, 1, 0, 1, 1, 1, 0, 1]
749
[28, 784, 1011, 144, 90, 71, 453, 1043, 493, 1032]
[28, 1011, 144, 71, 453, 1043, 1032]
28 1011
780 144
1061 71
776 453
546 1043
566 1032
------ 289
****** 289
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
[0, 0, 0, 1, 0, 1, 1, 1, 1, 1]
1000
[2, 4, 16, 256, 1303, 1582, 16, 256, 1303, 1582]
[256, 1582, 16, 256, 1303, 1582]
256 1582
562 16
1855 256
1459 1303
256 1582
------ 562
****** 562
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
[0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1]
1234
[567, 1735, 2809, 335, 4200, 1678, 2713, 1706, 2403, 1553, 691]
[1735, 4200, 2713, 1706, 691]
1735 4200
1794 2713
1676 1706
3075 691
------ 3214
****** 3214
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072]
[0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
258008
[47, 2209, 934168, 1286884, 530401, 937704, 970633, 414155, 1077376, 684880, 931737, 1296608, 10167, 784551, 516036, 1274729, 797811, 398022]
[1286884, 530401, 970633, 414155, 1077376, 684880, 931737, 1296608, 784551, 516036, 1274729, 797811, 398022]
1286884 530401
17681 970633
95694 414155
785656 1077376
232714 684880
851514 931737
987871 1296608
895051 784551
1274729 516036
920687 1274729
697698 797811
795380 398022
------ 1296608
****** 1296608
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]
[0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]
7386
[7, 49, 2401, 2941, 6691, 4261, 6262, 2448, 1847, 6002, 4992, 3713, 2227]
[49, 2941, 6691, 6262, 2448, 4992, 3713, 2227]
49 2941
3756 6691
822 6262
6012 2448
2472 4992
3934 3713
2843 2227
------ 702
****** 702
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]
[0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1]
7392
[7, 49, 2401, 5654, 384, 6989, 570, 7001, 5804, 3908, 5919, 6527, 3263]
[6989, 570, 7001, 5919, 6527, 3263]
6989 570
6296 7001
1230 5919
5658 6527
1731 3263
------ 1
****** 1
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192]
[0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1]
9990
[2, 4, 16, 256, 5590, 6243, 158, 4982, 2680, 8862, 5784, 4788, 5590, 6243]
[4, 16, 2680, 8862, 5784, 6243]
4 16
64 2680
1673 8862
9473 5784
1188 6243
------ 3362
****** 3362