2장(1)

암호학(cryptography) : 정보 보호를 위한 언어적&수학적 방법론을 다루는 학문

• 기밀성(confidentiality) : 부적절한 노출 방지
• 무결성(integrity) : 부적절한 변경 방지
• 가용성(availability) : 부적절한 서비스 거부 방지
• 부인봉쇄(non-repudiation) : 메시지를 전달/전달받았다는 사실 부인 방지

---

[정수연산] + - * /

 

나눗셈 : a = q * n + r

if a < 0, q와 r은 음수

r이 양수가 되려면, q-1, r+n

-> 컴퓨터에서는 + * q r 을 이용해 연산.

 

가분성(divisibility)

n|a : a는 n으로 나누어 떨어진다.

a|b이고 a|c라면, a|(m*b + n*c)

---

[최대공약수(Greatest Common Divisor)]

 

* 유클리드 알고리즘

gcd(a,0) = a

gcd(a,b) = gdb(b,r)

-> 이 때의 r은 a를 b로 나누었을 때의 나머지

 

Start Idea : 평소 최대공약수를 구할 때 인수분해를 이용하지만,

컴퓨터는 모든 소수를 알 수 없기 때문에 최대공약수를 구하는 새로운 방법 적용.

(64,60)

(60,4)

   .           => a와 b의 gcd = a와 a-b의 gcd

   .

(4,0)

 

#include <Stdio.h>

int gcd(int n1, int n2){
	int r = n1%n2;
    if(r == 0) return n2;
    else{
    	n1 = n2;
        n2 = r;
        gcd(n1,n2);
    }
}

int main(){
	int a,b;
    scanf("%d %d", &a, &b);
    printf("%d와 %d의 최대공약수 = %d\n", a,b,gcd(a,b));
}

 

* 확장된 유클리드 알고리즘

s * a + t * b = gcd(a,b)를 만족하는 s,t 계산 가능

-> s1 = 1, s2 = 0, t1 = 0, t2 = 1

Idea : r = a - b*q

 

#include <stdio.h>

int s1 = 1; int s2 = 0;
int t1 = 0; int t2 = 1;
int d;

void ext_gcd(int n1, int n2){
	int r = n1%n2;
    int q = n1/n2;
    int tmp;
    if(r == 0) {
    	d = n2;
        return;
    }
    else{
    	n1 = n2;
        n2 = r;
        tmp = s1;
        s1 = s2;
        s2 = tmp - s2*q;
        tmp = t1;
        t1 = t2;
        t2 = tmp - t2*q;
        ext_gcd(n1,n2);
    }
}

int main(){
	int a,b;
	scanf("%d %d", &a,&b);
    ext_gcd(a,b);
    printf("s * %d + t * %d = gcd(%d,%d) = %d 를 만족하는 s : %d, t : %d\n", a,b,a,b,d,s2,t2);
  }

 

* 디오판투스 방정식

ax + by  = c, d = gcd(a,b)

if d | c, 무수히 많은 해 존재.

else 해 존재 x.

> 특수해(particular solution) :

(a/d)s + (b/d)t = 1

x0 = (c/d)s

y0 = (c/d)t

> 일반해(general solutions)

x = x0 + k(b/d)

y = y0 - k(a/d)

#include <Stdio.h>
int s1 = 1; int s2 = 0;
int t1 = 0; int t2 = 1;
int d;

void gcd(int n1, int n2) {
	int r = n1 % n2;
	if (r == 0) {
		d = n2;
		return;
	}
	else {
		n1 = n2;
		n2 = r;
		gcd(n1, n2);
	}
}

void ext_gcd(int n1, int n2) {
	int r = n1 % n2;
	int q = n1 / n2;
	int tmp;
	if (r == 0) return;
	else {
		n1 = n2;
		n2 = r;
		tmp = s1;
		s1 = s2;
		s2 = tmp - s2 * q;
		tmp = t1;
		t1 = t2;
		t2 = tmp - t2 * q;
		ext_gcd(n1, n2);
	}
}

void Dio_gcd(int n1, int n2, int n3) {
	n3 = n3 / d;
	n1 = n1 / d;
	n2 = n2 / d;
	ext_gcd(n1, n2);
	int x0=s2*n3; int y0 = t2*n3;
	printf("특수해 : x0 = %d, y0 = %d\n", x0, y0);
	printf("일반해 : ");
	for (int i = 0; i < 5; i++) {
		printf("(%d,%d) ",x0 + i*n2, y0 - i*n1);
	}
	printf("\n");
}

int main() {
	int a, b, c;
	scanf_s("%d %d %d", &a, &b, &c);
	gcd(a, b);
	if (c%d != 0) printf("만족하는 해가 존재하지 않습니다.\n");
	else Dio_gcd(a, b, c);
}