전체 글 검색 결과

해당 글 9건

중국인의 나머지 정리

Chinese remainder theorem (CRT) 양의 정수들 $n_1, n_2 ,\cdots , n_k$가 $1\leq i \neq j \leq k$, $gcd(n_i,n_j)=1$(서로소)를 항상 만족할때, 아래의 연립합동식이 법 $M=n_1n_2\cdots n_k$에 대해 유일한 해를 가진다. $$x≡ a_1\pmod{n_1}$$ $$x≡ a_2\pmod{n_2}$$ $$\vdots$$ $$x≡ a_k\pmod{n_k}$$ 증명 ( 존재성과 유일성) $M=n_1n_2\cdots n_k$ $M_i = M/n_i$라고 할 때, $n_j\neq n_i$인 모든 $n_j$에 대해 $M_i ≡ 0 \pmod{n_j}$ 이다. $gcd(n_i,n_j)=1$이므로 (1외에 공유하는 인수가 없으므로) $g..
수학 2022. 3. 12. 13:48

오일러 정리

$a^{\varphi(n)}\equiv 1 \pmod{n}$ if $gcd(a,n)=1$ ($a$와 $n$이 서로소) $\varphi(n)$: $n$과 서로소인 $n$이하의 자연수의 갯수 증명 $Z_n^* = S = \{b_1, b_2, \cdots , b_{\varphi(n)}\}$ ($Z_n^*$은 양의 정수 n이하의 n과 서로소인 자연수 집합) $aS = \{ab_1, ab_2, \cdots , ab_{\varphi(n)}\}$ 일 때, S의 임의의 서로 다른 두 원소 $b_i$와 $b_j$ 는 n으로 나눈 나머지가 항상 다르다...(1) ($\because b_i, b_j$두 수의 차의 범위는 $0 < |b_i - b_j| \leq (n-2)$이다. 이 범위에서 $n$의 배수는 없다. 즉 $|b_..
수학 2022. 2. 22. 09:20

RSA

핵심 개념은 $x^{ed}≡x \pmod{pq}$이다. ($x$는 평문, $x^{e}(\mbox{mod } pq)$는 암호문, $e$: Encrytion exponent, $d$: Decryption exponent) x를 e로 암호화하고 d로 복호화 하면 다시 평문x가 나오며, 반대로 d로 암호화, e로 복호화 해도 평문 x가 나온다.(전자서명에서 사용) p와 q는 매우 큰 소수이다. 키사이즈 N비트는 pq를 말한다. $\varphi(pq) = (p-1)(q-1)$ $x^{\varphi(pq)} ≡ 1 (\mbox{mod }pq)$ 오일러 정리 $a^{\varphi(n)}\equiv 1 \pmod{n}$ if $gcd(a,n)=1$ ($a$와 $n$이 서로소) $\varphi(n)$: $n$과 서로소인..
정보보호론 2022. 2. 21. 19:13

베주 항등식

$\vert a \vert$+$\vert b \vert$>0 , a ∈ $\mathbb{Z}$, b∈ $\mathbb{Z}$ 일때, gcd(a,b)=d (d는 a,b의 최대공약수) 라면 아래 세가지 명제가 성립한다. 1. ax + by = d를 만족하는 정수 x,y가 존재 2. d는 정수 x, y에 대하여 ax + by꼴로 표현 될 수 있는 가장 작은 자연수이다. 3. 정수 x, y에 대하여 ax + by꼴로 표현 되는 모든 정수는 d의 배수이다. 증명. 집합 S={m | m = ax + by > 0, ab≠0 $\lor$ a+b≠0, a,b,x,y ∈ $\mathbb{Z}$}를 정의하자. $|a| =\begin{cases}\mbox{a*1 + b*0 ∈ S}&\mbox{if a > 0}\\\mbox{a..
수학 2022. 2. 12. 18:44