정수론 수업을 듣고 흥미로운 문제를 들었다.n차 합동방정식은 n개의 서로 다른 해를 가지는데 왜 RSA는 복호화가 잘 되는가?이거에 대해 알아본 결과.A를 특정 값으로 제한해서 복호화가 망가지는 걸 억제하는 것이였다. A값의 제한으로 여러 해 나오지 않게 하기m = pq (p, q는 소수)gcd(ϕ(m), k) = 1 에서 암호화는 c ≡ a^k (mod m) 이다.당연히 c는 양수(암호문은 항상 양수만 생각)이고 m에 대해 유일하다. 그럼 문제의 복호화는?x ≡ c^u ≡ a (mod m) 이다.이때 gcd(ϕ(m), k) = 1 이므로 선형방정식의 정리에 의해ku-ϕ(m)v = 1에서 해 ui, vi를 구할 수 있고 식을 변형하면 ku ≡ 1 mod(ϕ(m))이다.gcd(ϕ(m), k) = 1이므로 ..

오일러 ϕ 함수와 중국인의 나머지 정리ϕ(m) 계산하기m = 소수 pϕ(m) = m-1증명m을 제외한 모든 수가 서로소임m = p^kϕ(m) = ϕ(p^k) = p^(k-1)*(p-1)증명1~p^k 중 p의 배수를 뺴면 된다.즉, p^k - p^(k-1)이다.m = p^i * q^j (p, q는 소수)ϕ(m) = ϕ(p^i * q^j) = ϕ(p^i) * ϕ(q^j)증명-> m이 합성수라면 각 인수의 ϕ의 곱으로 계산할 수 있다.중국인의 나머지 정리m, n이 정수일 때 gcd(m, n) = 1이라면임의의 정수 b, c에 대해 연립합동방정식x ≡ b (mod m), x ≡ c (mod n)은 0 증명x ≡ b (mod m)의 해는 x = mk + b꼴, 이걸 다시 x ≡ c (mod n)에 대입해mk + ..

이진 탐색 트리(BST)모든 노드가 다음의 규칙을 만족하는 이진트리 왼쪽 subtree의 모든 값들은 현재 노드보다 작고 오른쪽 subtree의 모든 값들은 현재 노드보다 크다.(단, 보통은 중복 허용 안함) BST의 탐색 찾으려는 값에 따라 작으면 왼쪽, 크면 오른쪽으로 가기 만약 leaf에 도달해도 못 찾았다면 해당 요소가 없다BST의 삽입 적당히 탐색하고 알맞은 위치에 넣기BST의 삭제만약 leaf 노드라면 그냥 삭제만약 leaf 노드가 아니라면해당 노드 기준 왼쪽 subtree의 제일 큰 값또는 노드 기준 오른쪽 subtree의 제일 작은 값을 선택해 노드 삭제한 자리에 넣기연산의 시간 복잡도 최선평균최악탐색O(1)O(logN)O(N)삽입O(1)O(logN)O(N)삭제O..

이전 글: https://verybigsilver.tistory.com/106 [암호학](-)[RSA 구현 1]이론 암호학 중심 이론 정리https://verybigsilver.tistory.com/55 [암호학 둘러보기](8)[RSA]RSA: 비대칭키 암호화 방식디피-헬만과는 다르게 서명까지 지원해 안전함. (상대방의 공개키를 이용해 암호화하기verybigsilver.tistory.com GMP 라이브러리를 이용한 RSA 구현예전에 짰던 RSA 프로그램은 파이썬이나 C로 짰었는데,파이썬은 시간이 너무 오래 걸리고C는 visual studio 기준으로 long long 64비트밖에 지원을 하지 않아서 오버플로우가 났었다.따라서 C에서 큰 수의 연산을 가능하게 하는 GMP 라는 라이브러리로 다시 구현해 보..

기존까지 다뤘던 배열, 연결 리스트, 스택, 큐는 선형 자료구조!트리특징부모-자식 관계    root 노드를 제외하면 전부 부모 가짐    leaf 노드를 제외하면 전부 자식 가짐계층의 분화가 일어난다: 여러 레벨로 데이터가 구조화된다.탐색에 효율적임: O(logn)효율적인 삽입 연산현실 반영을 잘 함: 실제 현실의 구조와 많이 비슷함선형 구조보다 더 복잡한 구조 표현 가능배열과 연결 리스트의 단점 보완트리 ADT노드: 데이터가 저장된 요소엣지: 노드 사이를 잇는 선용어뿌리(root), 잎(leaf), 비단말(non-terminal)뿌리: 맨 위에 있는 노드잎: 맨 끝에 있는 자식이 없는 노드비단말: 뿌리도 잎도 아닌 노드부모(parent), 자식(child), 형제(sibling):부모: 어떤 노드를 ..

유클리드 호제법을 a, b에 적용할 때 나오는 나머지 b=r0, r1, r2...에서 모든 i에 대해 r(i+2) 먼저 유클리드 호제법에서 r(i) = r(i+1)q(i+1) + r(i+2) 다.유클리드 호제법에선 모든 r >= 0이고, q>0이므로0 그리고 q(i+1)를 기준으로 경우를 나눠 살펴보자.if q(i+1) = 1?r(i) = r(i+1)q(i+1) + r(i+2) = r(i+1) + r(i+2)이다.여기서 r(i+1) > r(i+2) 이므로2r(i+2) 따라서 q=1이면 r(i+2)if q(i+1) >= 2?r(i+2) = r(i) - r(i+1)q(i+1)에서 q(i+1) >= 2 이므로r(i+1)q(i+1) >= 2r(i+1)즉, r(i) = r(i+2) + r(i+1)q(i+1) >=..

오일러 ϕ 함수ϕ(m) = {a| 1예)ϕ(1) = 1ϕ(2) = 1ϕ(3) = 2 ... 소수 p에 대해 a !≡ 0 (mod m) 을 만족하는 1~ϕ(m)개의 b의 배수 bna (mod m)는 1, 2, ..., bn을 재배열한 것과 같다.증명gcd(b1, m) = 1이면 gcd(ab1, m) = 1이다.이때 bja, bka가 법 m에 대해 합동이라 가정한다. (1bja ≡ bka (mod m)이므로 m|(j-k)a이다. p∤a 이므로 소수의 가약성에 의해 p|(bj-bk)이다.그러나 (1따라서 bj-bk = 0 -> bj = bk이다m에 대해 합동인 수 bja = bka이므로 합동이면 전부 같은 숫자다.0이 아닌 ϕ(m)개의 합동이 아닌 수 목록은 1~ϕ(m)이므로 따라서 재배열이다.-> 즉, b1..

이론 암호학 중심 이론 정리https://verybigsilver.tistory.com/55 [암호학 둘러보기](8)[RSA]RSA: 비대칭키 암호화 방식디피-헬만과는 다르게 서명까지 지원해 안전함. (상대방의 공개키를 이용해 암호화하기 때문)과정메세지 보내는 A, 메세지 받는 B이고 공개된 파라미터 e가 있다.B의 공verybigsilver.tistory.com 수론 중심 이론 정리https://verybigsilver.tistory.com/100 참고 구현 일단 코드를 대충 짜면 이렇게 된다.def extended_gcd(a, b): if b == 0: return 1, 0 # 해는 (1, 0) x1, y1 = extended_gcd(b, a % b) # 재귀 호출 ..

소수 p에 대해 a !≡ 0(mod p) 을 만족하는 a의 배수 (mod p)는 1, 2, ..., p-1을 재배열한 것과 같다.증명a, 2a, ..., (p-1)a 는 p의 배수가 아니다.이때 ja, ka가 법 p에 대해 합동이라 가정한다. (1ja ≡ ka (mod p)이므로 p|(j-k)a이다. p∤a 이므로 소수의 가약성에 의해 p|(j-k)이다.그러나 (1따라서 j-k = 0 -> j = k이다p에 대해 합동인 수 ja = ka이므로 합동이면 전부 같은 숫자다.0이 아닌 p-1개의 합동이 아닌 수 목록은 1~p-1이므로 따라서 재배열이다.즉, a, 2a, ..., (p-1)a (mod p)와 1, 2, ..., p-1 (mod p)는 순서만 다르지 같은 배열이다. 페르마의 소정리p가 소수이고 a..

561이 카마이클 수인지 판별하시오카마이클 수란, gcd(a, m) = 1일때, a^(m-1) ≡ 1 (mod m)를 만족하지만 소수가 아닌 m을 말한다.따라서m이 합성수이고gcd(a, m) = 1인 모든 a에 대해 a^(m-1) ≡ 1 (mod m)를 만족하는지 보이면 된다.1.561이 합성수?561 = 3 * 11 * 17이므로 합성수gcd(a, 561) = 1인 모든 a에 대해 a^(560) ≡ 1 (mod 561)?gcd(a, 561) = 1 이고 561의 인수가 각각 서로소이고 소수이므로,    gcd(a, 3) = 1    gcd(a, 11) = 1    gcd(a, 17) = 1 만족한다.따라서 3, 11, 17에 대해서 페르마의 소정리를 사용할 수 있다.    a^2 ≡ 1 (mod 3) ..