Modular Exponentiation

#역원을 구하기 위한 알고리즘
def extended_gcd(a, b):
    #초기 설정을 위한 초기화
    r1, r2 = a, b
    s1, s2 = 1, 0
    t1, t2 = 0, 1
    
    while(r2 > 0):
        q = r1 // r2
        r = r1 - q * r2 #q는 r2로 r1을 나눈 몫, r은 그 나머지
        r1, r2 = r2, r #r1은 r2로, r2는 r로 초기화
 
        s = s1 - q * s2 #q는 s2로 s1을 나눈 몫, s는 그 나머지
        s1, s2 = s2, s #s1은 s2로 s2는 s로 초기화
 
        t = t1 - q * t2 #q는 t2로 t1을 나눈 몫, t은 그 나머지
        t1, t2 = t2, t #t1은 t2로 t2는 t로 초기화

    return s1 #a*y1 = 1 mod b이므로 s1을 반환
    #s1이 a의 역원이 됨

def crt(p, q, a, b): # x = a mod p, x = b mod q
    m1 = q #m1 = p*q/p
    m2 = p #m2 = p*q/q
    y1 = extended_gcd(m1, p) #m1*y1 = 1 mod p에서 y1은 m1의 역원
    y2 = extended_gcd(m2, q) #m2*y1 = 1 mod q에서 y2는 m2의 역원
    x = y1*a*m1 + y2*b*m2 #x의 값을 구함
    while x <= 0: #x가 음수라면
        x += m1 * m2 #modulo연산 수행(mod m1*m2)
    return x #x반환

def mod_exp(a, e, n):  #a^e mod n
    x = change_bin(e) #e를 이진수로 표현
    s = 1
    for i in range(0, len(x)):
        if x[i] == '1': #x[i]이 1이라면
            r = s*a % n #multply함
        else: #x[i]이 0이라면
            r = s #그대로 초기화
        s = r*r % n #square함
    return r

#e값을 이진수로 변환하여 출력
def change_bin(e):
    binary = ""
    while e >= 1:
        data = e % 2 #나머지
        e = e // 2 #몫
        if data == 1: #나머지가 1이라면
            binary += '1' #이진수 1로 초기화
        else: #나머지가 0이라면
            binary += '0' #이진수 0으로 초기화
    #영상에서 나온 알고리즘을 적용하기 위해 이진수데이터를 반대로 나열
    binary = binary[::-1]
    return binary

print(mod_exp(3, 12345, 97))
print(mod_exp(5, 123456789012345, 976))
print(mod_exp(7, 1234567890123456789, 12345))
print(crt(10, 21, 1, 2))
print(crt(257, 293, 11, 13))
print(crt(123, 457, 1, 34))