minkylee

Ring Structure 복습비어있지 않은 집합 R 위에 덧셈과 곱셈이라는 두 개의 닫힌 이항 연산(binary operator)가 정의되어 있을 때 $$ 이 Ring이 되려면 R의 원소 a, b, c에 대해 다음 조건들이 모두 만족되어야 한다.a + b = b + a (덧셈 교환법칙)a + (b + c) = (a + b) + c (결합 법칙)$\exists \ z \ (\in R)$ such that a + z = z + a = a (덧셈 항등원)for each $a \in R, \exists \ b$  with a + b = b + a = z (덧셈 역원) ==> 여기까지 Abelian group의 조건$a \ \cdot \ (b \ \cdot \ c)$  = $ (a \ \cdot \ b ) \ ..

암호화의 종류대칭키 암호 시스템 : 송신자와 수신자가 같은 비밀키를 사용하여 데이터를 암호화하고 복호화 하는 방식공개키 암호 시스템 : 송신자와 수신자가 각각 다른 키 사용, 송신자는 수신자의 공개키로 메시지 암호화, 수신자는 자신의 개인키로 복호화Bob이 Alice에게 평문을 보내려 한다.Bob은 자신이 가지고 있는 Alice의 공개키를 통해 암호화한다.암호문을 Alice에게 보낸다.Alice는 자신만 가지고 있는 개인키를 가지고 복호화 한다.암호화 방법서로 다른 두 소수 p와 q를 선택한다. 두 소수를 곱해서 n을 계산한다. (n = pq) r은 $\mathbf{\phi(n)}$ 이 된다.r이 공개키의 모듈이 된다.r은 $\phi(n) = \phi(p) * \phi(q) = (p-1)(q-1)$r과 ..

Cyclic Group 정의그룹 G가 cyclic이 되기 위해서는 G 안에 생성자(generator)라고 불리는 특정 원소 x가 존재해야한다.G의 모든 원소 a는 x의 거듭제곱으로 만들 수 있다. $a \in G, \ a = x^n, \ n \in Z$ Cyclic Group $Z_4$가 있다. 1과 3은 생성자이고 0과 2는 생성자가 아니다.그룹 G의 원소 a의 거듭제곱으로 만든 집합 S는 G의 Subgroup이다. 닫힘성과 역원을 만족하기 때문이다.이 Subgroup을 subgroup generated by a 라고 하고 $$ 라고 쓴다.예시$$ 그룹 H에 대해$[0]^1 = [0]^2 = [0]^3 = [0]^4 \rightarrow = \{0\}$$[1]^1 = [1], [1]^2 = [2], ..

사상 (morphism)수학적 구조를 보존하는 함수의 개념을 추상화한 것 말이 너무 어렵다.사상은 수학에서 특정한 구조를 유지하면서 한 구조에서 다른 구조로 연결하는 함수이다. 어떤 규칙에 따라 두 수학적 대상이나 집합을 이어주는 다리 역할을 한다.집합의 사상은 일반적인 함수 -> 숫자 1을 2로 보내고, 3을 4로 보내는 규칙이 있을 때 이것도 하나의 사상이다.Group의 사상은 Group의 구조를 보존하는 함수이다.예를 들어, 덧셈 구조가 있는 숫자 집합에서 덧셈 결과를 동일하게 유지하면서 다른 집합에 매핑한다.G에서 H로 가는 함수 f가 사상이 되기 위해서는 G에서의 덧셈이 H에서도 동일하게 유지되어야 한다.덧셈을 먼저 하고 함수 f를 적용한 결과 f(a + b) 와 각각 f(a)와 f(b)를 구해..

https://minkylee.tistory.com/50 K$ : 집합 K" data-og-host="minkylee.tistory.com" data-og-source-url="https://minkylee.tistory.com/50" data-og-url="https://minkylee.tistory.com/50" data-og-image="https://scrap.kakaocdn.net/dn/JjQBF/hyXlJUIJw9/b2tGCGzk2eXffuEWI6wTB0/img.png?width=800&height=800&face=0_0_800_800,https://scrap.kakaocdn.net/dn/bqGo2o/hyXlIBwDi9/3502Q8qvnHpkm2wHcUPy1K/img.png?width=800&..

r0, r1 두 수의 최대공약수를 구하는 방법 작은 수에서는 쉽다. 두 수를 소인수분해해서 공통 소인수를 찾고 그걸 곱해준다. 하지만 큰 수에 대해서는 복잡해진다. 어떻게 쉽게 계산할 수 있을까?  $gcd(r_0, r_1) = gcd(r_0 - r_1, r_1)$핵심 아이디어큰 수의 gcd를 구하는 문제를 점점 더 작은 수의 gcd를 구하는 문제로 바꾼다.이 과정을 재귀적으로 반복한다.마지막에 $gcd(r_1, 0)$ 이 나올 때 $r_1$이 원래 gcd이다.긴 숫자일수록 복잡도는 입력 비트 수에 선형적으로 증가한다.증명1. a와 b의 최대공약수 d가 있다. d는 a와 b 모두를 나눌 수 있다.2. a는 $a = kb + r$이라는 식으로 표현 가능하다. 여기서 k는 a를 b로 나눈 몫, r은 a를 b..

complete set of residues : 1보다 큰 자연수 n에 대해 어떤 정수들의 집합의 원소들을 n으로 나눴을때 나머지가 모두 다를 때reduced set of residues : complete set of residues 중에서 n과 서로소인 수들의 집합ex) n = 10일 때complete set of residues {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}reduced set of residues : {1, 3, 7, 9}reduced set of residues의 원소의 수를 Euler Phi (Totient) Function $ \phi (n) $ 이라고 한다. $\phi (10) = 4$ 이고 그 집합은 {1, 3, 7, 9}가 된다. 정의1부터 n 까지의 정수 가운..

Contruence Modulo n (모듈로 합동)정의n이 1보다 큰 자연수이고, 정수 집합에 속하는 a, b에 대해 n이 a-b를 나누면 (n|(a-b)) 즉, $a = b + kn$ 이면 a 와 b가 모듈로 합동이다.$ a \equiv b (mod n) $ 이라고 쓴다.ex) $ 17 \equiv 2 (mod 5) $  17 = 2 + 3 X 5정리1모듈로 합동은 정수 집합 $Z$ 위에서 equivalence relation(동치관계)이다.  Equivalence ClassesEquivalence relation은 어떤 집합을 분할할 수 있다.$n$ 이 2 이상인 경우 정수집합 $Z$ 를 n개의 equivalence class로 나눌 수 있다.ex) n = 6 일 때, 7과 1은 나머지 1에 대해서 ..