만든 블로그

Montgomery Form 위 이미지에 있는 계산 방식은 Montgomery From 이라고 하는 계산방법이다. 몽고메리 폼에서의 a` = aR mod N와 b` = bR mod N을 곱하면 (aR mod N) * (bR mod N) = (abR)R mod N 이고, 이를 몽고메리 폼에 맞게 하기 위해 R^(-1)을 곱해준다. (abR)R*R^(-1) mod N =(abR) mod N 이러한 계산과정은 R^(-1)을 곱하고 N을 나눠야 하기 때문에 느리다. 하지만 아래의 알고리즘을 통하여 구하면 비트 쉬프트 연산을 통해 빠른 계산으로 구할 수 있다. Montgomery Reduction Algorithm아래의 수식은 몽고메리 감산 알고리즘으로 T = (aR mod N) * (bR mod N)을 (abR..

이진 탐색 알고리즘이란? 이진 탐색 알고리즘이란 정렬된 배열을 탐색 범위를 절반으로 줄여나가면서 탐색하는 알고리즘이다. 예시 오름차순으로 정렬된 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 배열로 1을 찾는 예시를 들어보겠다. 먼저 배열의 중간 값을 배열의 길이와 2를 나눈 몫의 값에 위치한 값이라고 하자. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 의 중간 값인 5와 1을 비교하고, 1이 5보다 작으므로 탐색범위를 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 에서 [0, 1, 2, 3, 4] 으로 줄인다. 이제 [0, 1, 2, 3, 4]에서 중간 값인 2가 1보다 크므로 탐색 범위를 [0, 1] 로 줄인다. [0, 1] 에서 중간 값이 우리가 찾..

개요일반적으로 매우 큰 지수승의 수에 대해서 연산하는 것은 많은 자원을 이용해야한다. 특히 모듈러 연산 x**e (mod n) 대해서 e가 크면 클수록 매우 많은 공간과 시간을 써야한다. 하지만 모듈러 연산의 성질을 이용하여 연산의 속도를 매우 크게 향상 시킬 수 있다.모듈러 연산의 성질 이 모듈러 연산에 대해서 여러가지 성질이 있지만 이 글에서 다룰 성질은 단 두가지이다.빠른 모듈러 거듭제곱 연산과정과 원리아래의 예시로 설명하겠다.먼저 우리가 나눌 대상인 x의 지수 7를 2의 제곱의 합으로 나타낸다.모듈러 연산의 성질을 이용하여 위와 같은 형태로 변환하고 계산한다. 기존 지수의 대한 연산은 밑을 그 지수의 계수만큼 곱하는 연산이 이루어진다. 하지만 모듈러연산에서는 지수에 대한 연산을 위와같이 변환하여 ..

버블 정렬 버블 정렬이란? 인접한 두 원소의 크기를 비교하여 대소관계에 따라 위치를 교환하거나 교환하지 않음으로 오름차순이나 내림차순으로 데이터를 정렬하는 알고리즘이다. 예시 위의 배열을 버블정렬을 통해 오름차순으로 한번 정렬해 보자 인접한 두 값을 비교하여 큰 값이 왼쪽에 있다면 (큰 값, 작은 값) 두 개의 값의 위치를 서로 바꿔주고, 반대되는 경우 (작은 값, 큰 값) 자리를 바꾸지 않는다. 이 과정을 수행하면 배열에서 가장 큰 값이 배열의 가장 오른쪽에 위치하게 된다. 배열에 가장 큰 값인 5를 오른쪽에 옮겼던 과정을 다시 수행한다. 이때 5는 이미 제자리를 찾았으므로 비교대상에서 제외한다. 비교를 수행하여 배열에서 두 번째로 큰 값인 4가 5 다음에 위치하게 된다. 4와 5가 제자리를 찾았으므로..

유클리드 알고리즘유클리드 알고리즘이란?유클리드 알고리즘이란 두 정수의 최대 공약수를 효율적으로 구하는 방법으로써 다음 정리를 이용한다,a = bp + r (0 gcd(a, b) 는 a 와 b의 최대공약수를 의미한다. gcd(a, b) = gcd(b, r) 이 성립함을 증명예시28과 24의 최대 공배수를 구해보면28 = 24 * 1 + 4gcd(28, 24) = gcd(24, 4)24 = 4 * 6 + 0gcd(24, 4) = 4즉, gcd(28, 24) = gcd(24, 4) = 4이므로 28과 4의 최대 공배수가 4 임을 알 수 있다.구현 (파이썬)gcd(a, b) = gcd(b, r) 이라는 것을 이용하여 계속반복해보면 위와같은 점화식이 나오는 것을 알 수 있다.그리고 위의 점화식이 유클리드 알고리즘..