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

지금까지 C로 BIGINT관련 함수들을 작성해 봤고, 큰 정수와 관련된 연산들은 대부분 다룬 것 같다. 이것들은 다음과 같이 활용될 수 있을 것이다. PC가 아닌 Embedded System에서 C로 큰 정수의 연산을 해야하는 곳 PC에서 Java의 BigInteger클래스를 사용하고 있는데, 좀 더 빠른 속도를 내기 위해서 ..

2.15. 소수(Prime Number) 소수는 1과 그 자신만을 약수로 가지는 1보다 큰 자연수이다. 예를 들어, 1,3,5,7,11,17,19... 이런 수들이다. 소수는 암호학에서 비대칭키 알고리즘으로 현재까지 가장 많이 사용되고 있는 RSA암호의 근간이 되는 수이다. 자연수가 무수히 많듯이 소수도 무한히 많다. 수학..

2.14. 난수 (Random Number) 이번 장에서는 의사난수(擬似亂數, pseudo random number)라고 불리는 무작위 수, 즉 난수의 생성에 대해 다룬다. 난수는 무작위 수이다. 규칙성이 없어야 하고, 확률적인 분포에 치우침이 없는 수이다. 그러나, 의사난수는 규칙성이 있다. 확률적인 분포만이 치우침이 없..

2.13 기수변환 이번 장에서는 BIGINT 수를 여러가지 기수로(진법) 변환하는 알고리즘에 대해서 다룬다. 우리의 일상생활에서는 10진수가 주로 쓰이고 있으나, 컴퓨터는 2진수 체계를 기반으로 움직인다. 2진수는 두 개의 숫자 0과 1로 표현될 수 있으며, 10진수는 0에서부터 9까지의 수로 표현..

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자리 이하의 몫이 나온다. 나눗셈에 대한 알고리즘도 덧셈,뺄셈,곱셈과 ..