컴퓨터 프로그래밍(암호학, 알고리즘)

2.12 거듭제곱 이번 장에서는 A가 BIGINT, e가 양의정수일 때, Ae를 구한는 알고리즘을 알아본다. A16을 구하기 위해서는 A를 15번 곱해도 된다. 그러나, 더 좋은 방법이 있다. 아래처럼 구하는 것이다. A16 = (((A2)2)2)2 즉, A2, A4, A8, A16의 차례로 구하는 것이다. 일반화해서 지수가 e일 때 어떻게 간..

2.11 비트 수 세기 비트의 구성이 어떻게 되어 있는지를 파악하는 두 가지 기능을 작성한다. 하나는 BIGINT수에 대해 '1'인 비트가 몇 개 있는지를 세는 함수인 bitCount(음수의 경우는 '0'인 비트 수), 다른 하나는 수를 나타내기 위해 필요한 비트 길이를 나타내는 bitLength. 예를 들어 십진수 17은..

2.10 비트 연산(bitwise operation) BIGINT의 비트별 연산함수를 만들어 본다. 비트별 연산은 다음과 같다. bit_andbit_orbit_xorshiftleftshitright 비트별 논리연산인 and, or, xor는 두 BIGINT의 각 비트값에 따라 아래와 같은 결과값을 가진다. p q and or xor 0 0 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 두 BIGINT의 길이가 서로 다..

2.9 최대공약수(gcd) u, v가 둘 다 0이아닌 정수 일 때, u와 v를 모두 나누는 가장 큰 정수가 최대공약수(gcd, greatest commond divisor)이다. 최대공약수는 다음과 같은 특성을 가진다. gcd(0,0) = 0 gcd(u,0) = |u| gcd(u,v) = gcd(v,u) gcd(-u,v) = gcd(u,v) gcd는 유클리드 알고리즘을 이용해서 비교적 쉽게 구할 수 있다..

2.8 나머지(mod) 나머지식 산술에 대해서 알아보자 a가 정수일때, 자연수 m에 대해서 다음과 같은 식이 성립한다고 할 때, a = qm + r, 0 ≤ r < m r을 "a를 m으로 나눌 때의 나머지라 하고, r = a mod m 혹은 a ≡ r mod m으로 표현한다. 나머지식 산술은 덧셈, 뺄셈, 곱셈에 대해 유효한데 하나씩 구현..

2.7 나눗셈(divide) 큰 수에 대한 나눗셈을 생각해 보자. 곱셈의 경우는 앞 장에서 설명한 바와 같이, m자리와 n자리의 두 수를 곱하면 (m+n)자리의 결과값이 나온다. 나눗셈에서는 (m+n)자리의 수를 n자리 정수로 나누면, m자리 이하의 몫이 나온다. 나눗셈에 대한 알고리즘도 덧셈,뺄셈,곱셈과 ..

2.6 제곱(square) 제곱은 같은 수끼리 곱하는 것으로 이미 구현된 곱셈을 사용할 수 있으나, 같은 수를 곱할 때 생기는 규칙성을 이용해서, 보다 효율적인 계산을 할 수 있다. 45261의 제곱을 구하는 것을 예로 들어보자. 답은 2048558121가 나와야 할 것이다. 일반적으로 연필로 계산하는 방식대..

2.5 곱셈(multiply) 덧셈/증가 그리고 뺄셈/감소에 이어 곱셈에 대해 알아보자. 곱셈도 알고리즘이 그리 어렵지 않다. 덧셈 뺄셈과 마찬가지로 손으로 곱셈을 계산하는 방법을 그대로 구현하면 된다. 수행횟수는 덧셈/뺄셈이 O(n)정도를 보이는데 반해, 곱셈은 O(mn) 정도를 보인다. (m과 n은 곱..

2.4 감소(decrese) 1만큼 감소시키는 함수이다. 1을 증가시키는 increse의 경우에도 add를 사용할 수도 있으나 효율성을 생각해서 별도 구현을 했듯이, decrese함수도 subtract함수로 구현할 수 있으나, 별도로 구현한다. 기본 원리는, 주어진 BIGINT값에 대해 가장 작은 자릿수를 -1해주고, 만약에 borrow..

2.3 뺄셈 앞 장에서 큰 수에 대한 첫 번째 연산으로 덧셈을 알아 봤다. 이번 장은 뺄셈이다. 뺄셈에 대한 알고리즘은 덧셈과 유사하다. 같은 자리끼리 더하는 것 대신에 빼주면 되고, 덧셈에서 올림이 발생한 반면, 뺄셈에서는 빌림(borrow)이 발생하는 것이 차이다. 뺄셈 알고리즘 이 알고리..