[RSA] Extended Euclidean Algorithm - 확장된 유클리디안 알고리즘

RSA를 알기 위해서는 확장된 유클리디안 알고리즘과 페르마 + 오일러 정리를 알고 있어야 한다. 

 

그런데 확장된 유클리디안 알고리즘이 계산을 어떻게 하는지 도저히 감을 잡지 못했다. 

페르마 + 오일러의 정리는 그냥 공식이 나와있고 그 공식이 뭔지만 알면 된다. (물론 증명은 따로 더 이해하려 하지 않았다. 사실 이해하려 했다가 무슨 말인지 몰라서 중간에 그만뒀다.)

 

그런데 확장된 유클리디안 알고리즘의 경우 문제를 풀기 위해서는 반드시 작동 원리를 알아야 했는데 간단한 계산의 연속임에도 불구하고 대체 뭘 계산하는건지 감이 잡히지 않았다. 

 

오기가 생겨서 똑같은 영상을 최소 5번~6번정도는 돌려본것 같은데, 정말 어떻게 된건지는 모르겠지만 대여섯번쯤 볼때쯤에 어떻게 하는지 감이 왔다. 그리고 몇몇 문제를 풀어보았는데 맞았다. (왜 이 간단한 원리를 헤맸던걸까. 항상 이해하고 나면 이런 생각이 든다. )

 

가장 잘 정리된 영상이 아래 2개이다. (참고로 2번째 영상에서는 실제 d^-1값 즉 역원을 어떻게 구하는지는 나와있지 않다. 다만 과정이 상당히 잘 설명되있다. 그래서 1번째 영상을 보면 실제 우리가 문제를 풀 적에 x값을 즉 역원을 어떻게 구하는지가 상당히 잘 나와있다. 답을 하나로 도출해낼 수 있는 영상이다.)

 

참고: 1번째 영상에서 가장 마지막 계산을 할적에 답으로 나온 x인 -5를 갑자기 43 -5 를 해서 38이라고 결론내리는 부분이 있다. 조금만 생각해보면 즉 우리가 지금 하는것이 modular연산이라는 것을 생각하면 0~43의 범위로 맞춰주기 위해서 43에서 -5를 해줘도 문제가 없다는 것을 알 수 있을 것이다. 왜냐면 modular는 수에 대해서 circular한 측면이 있기 때문이다. 비유가 적절할지 모르겠지만 시계를 떠올리면 된다. 

 

결론: 이해안되면 그냥 될때까지 시도 -> 시도 -> 방법 바꿔보기 -> 시도 -> 시도 -> 효율적으로 학습해보기 -> 시도 -> 시도 -> 그냥 무한시도해보면 된다. 그러면 이해된다. 

 

그리고 참고로 RSA는 직접 문제 한번 딱 하나만 풀어보면 바로 이해될 수 있다. 생각보다 간단하다.

 

https://www.youtube.com/watch?v=fz1vxq5ts5I 

https://www.youtube.com/watch?v=hB34-GSDT3k