원시근과 지표g가 소수 p의 원시근이라면g, g^2, ..., g^(p-1) ≡ 1, 2, ..., p-1 (mod p)의 재배열즉 g의 지수와 1~p-1 사이의 값이 일대일대응이다.이때 g^(e) ≡ a (mod p)의 e를 mod p에 대한 a의 지표라고 정의한다.$$g^{I_{p, \ g}(a)} \equiv a \ (mod \ p)$$만약 p, g가 명확한 경우, I(a)로 간략화할 수 있다.성질곱셈법칙: I(a) + I(b) ≡ I(ab) (mod p-1)g^I(ab) ≡ ab≡ g^I(a) * g^I(b) ≡ g^(I(a) + I(b)) (mod p)이때 지수는 1~p-1사이의 값이므로,I(a) + I(b) ≡ I(ab) (mod p-1)거듭제곱 법칙: I(a^k) ≡ kI(a) (mod p-..

소수 p, gcd(a, p) = 1인 a에 대해, 페르마의 정리에 의해,a^e ≡ 1 (mod p)인 e는 항상 존재한다. (p-1)그럼 가장 작은 e도 항상 p-1인가? -> 그건 아님 위수위수: 소수 p, gcd(a, p) = 1인 a에 대해, a^e ≡ 1 (mod p)를 만족하는 가장 작은 e(단 e>=1)표기는 $e_p(a)$로 함. 원시근: 위수가 p-1인 a 위수의 나눔성질소수 p, gcd(a, p) = 1일때, 위수 e는 a^n ≡ 1 (mod p)을 만족하는 n에 대해e|n을 만족한다.(특히, 페르마의 소정리에 의해 e|(p-1)이다.)증명위수의 정의에 의해 a^e ≡ 1 (mod p) 이다.그리고 어떤 수 n = eq + r에 대해 a^n ≡ 1 (mod p)이라 하자.(단, 0a^n ..

르장드르 기호p = 홀수 소수일때합동으로 계산(kp+r/p) = (r/p)(a/p) = (a-p/p)이건 특히 큰 수에서 인수분해가 힘들 때 숫자를 줄일 수 있다.제곱은 언제나 1(a^2/p) = (a/p)*(a/p)이므로(a/p)값에 상관 없이 항상 값이 1이 나온다.이차상호법칙이차상호법칙 - 1홀수 소수 p에 대해 (-1/p)는p ≡ 1 (mod 4) 일때 1p ≡ 3 (mod 4) 일때 -1이차상호법칙 - 2홀수 소수 p에 대해 (2/p)는p ≡ 1 or 7 (mod 8) 일때 1p ≡ 3 or 5 (mod 8) 일때 -1이차상호법칙 - 3홀수 소수 p, q에 대해 (q/p)는p ≡ 1 (mod 4) or q ≡ 1 (mod 4) 일때 (p/q)p, q ≡ 3 (mod 4) 일때 -(p/q) 야코비..

F(n): n의 모든 양의 약수의 ϕ값의 합예) F(6) = ϕ(1) + ϕ(2) + ϕ(3) + ϕ(6) = 1+1+2+2 = 6 F(n)의 성질 곱셈적 함수 성질gcd(m ,n) = 1 이라먄 F(mn) = F(m)F(n)이다.증명 n의 양의 약수를 d1, d2, ..., dr m의 양의 약수를 e1, e2, ..., es라 하자. mn의 약수는 d, e를 조합한 것과 같다. 따라서 F(mn) = ϕ(d1e1) + ϕ(d1e2) + ... + ϕ(dres) 이때, gcd(m, n) = 1 이므로, 모든 d, e에 대해 gcd(d, e) = 1이다. 따라서 ϕ(de) = ϕ(d)ϕ(e) 이다. (합성수라도 쪼개서 계산하면 됨.) F(mn) = ϕ(d1)ϕ(e1) +..

이차상호법칙 - 1홀수 소수 p에 대해 (-1/p)는 p ≡ 1 (mod 4) 일때 1 p ≡ 3 (mod 4) 일때 -1 증명p ≡ 1 (mod 4) 이라면p = 4k+1 이고 오일러 판정법에 의해-1^((4k+1-1)/2) = -1^(2k) = -1^(짝수)따라서 (-1/p) ≡ 1 (mod p)p ≡ 3 (mod 4) 라면p = 4k+3이고 오일러 판정법에 의해-1^((4k+3-1)/2) = -1^(2k+1) = -1^(홀수)따라서 (-1/p) ≡ -1 (mod p) 이차상호법칙 - 2홀수 소수 p에 대해 (2/p)는 p ≡ 1 or 7 (mod 8) 일때 1 p ≡ 3 or 5 (mod 8) 일때 -1 증명(p-1)/2를 P라고 두겠다.p ≡ 3 (mod 8)라면p = 8k+..

해시 테이블Map을 구현하는 방법 중 하나구성 요소해시 함수bucket: 자료가 저장되는 배열 데이터 관리 insertkey를 해시 함수에 넣고 -> mod 연산을 한 뒤 -> 그 값을 인덱스로 사용해 자료, 해시값을 저장예) 크기가 8인 버킷에 (value = 'abc', key = 9)인 데이터를 저장하고 싶다면 1. 해시함수에 9를 넣어 hash = 14라는 값이 나왔다고 하자. 2. 14 ≡ 6 (mod 8) 이므로 인덱스는 6이다 3. 해당 인덱스에 key, value, hash를 저장한다 collision handling인덱스가 중복되는 충돌이 발생하는 경우경우 1: 같은 해시 값이 나왔을 때경우 2: 다른 해시 값이지만 mod 연산에서 인덱스가 같을 때충돌을 처리하는 방법ch..

Mapkey-value 쌍의 ADT-> key를 이용한 빠른 선형 탐색에 특화됨key: 탐색을 위한 값value: 실제 저장할 데이터연산get(key)insert(key, value)remove(key)Map VS 우선순위 큐 map은 key로, 우선순위 큐는 우선순위로 검색하나 사용 목적이 약간 다름 map: 빠른 탐색 우선순위 큐: 순서대로 프로세스 실행해시 함수암호학에서도 이용됨 (암호학 둘러보기 9 참고)특징비가역적해시 -> 평문은 매우 힘듬출력값의 길이가 고정됨랜덤이 아님같은 입력을 넣으면 무조건 같은 출력이 나옴좋은 해시의 특징충돌이 적음다른 입력으로 같은 해시 값이 나오는 것을 충돌이라 한다.좋은 해시는 '최대한' 다른 입력이면 다른 값이 나오는게 좋다.(물론 ..

trie자동완성 등에 특화된 자료구조-> 접두사를 기준으로 빠른 탐색 가능 그냥 배열 vs trie단어 탐색: N개의 단어가 있을 때 L길이의 단어를 찾는다면 배열: N개의 단어에 대해 L길이만큼 다 맞는지 확인 -> O(LN) trie: 단어 길이만큼만 분기를 따라가면 됨 -> O(L)접두사 탐색: P길이의 접두사가 주어지고 N개의 단어 중 찾는다면 배열: P길이의 접두사 비교를 N개의 단어에 대해 모두 확인 -> O(PN) trie: 얘도 접두사 만큼만 따라가면 됨 -> O(P) (= O(L))메모리 차지 배열은 그냥 저장하면 되지만 trie는 노드별로 분기를 저장해야 되기 때문 예) 영어를 저장하는 trie는 각 노드마다 26개의 공간이 있어야 한다. ..

heap완전 이진트리니 배열로 구현하기 편하다.(자료구조 12 참고)여기서는 계산상의 편의를 위해 1부터 인덱싱하는 Max힙을 만들겠다. 기본 골조자료를 저장할 배열을 만든다.#define MAX_SIZE 100int heap[MAX_SIZE];int heapSize = 0;그리고 인덱스에 있는 값을 바꿔야 하므로, swap도 정의하겠다.void swap(int* a, int* b){ int tmp = *a; *a = *b; *b = tmp;} 부모-자식 연산인덱스를 가지고 부모 or 자식의 인덱스 계산int parent(int i){ return i/2;}int left(int i){ return 2*i;}int right(int i){ return 2*i+1;} bul..

트리가 complete binary tree이므로N개의 노드가 있을 때 주어진 트리의 최대 높이 H = logN 높이가 h인 부분 트리의 개수 = $\lceil{\frac{n}{2^{h+1}}}\rceil$ 이때 bubbling down이므로 leaf는 계산하지 않는다.(왜냐하면 가장 마지막 부모 노드부터 시작하니까)즉, 높이 h = 0인 노드는 무시하고 시간복잡도를 계산해야 한다.높이가 h인 노드에서 bubbling down으로 내려갈 때 연산은 최대 h번 한다고 할 수 있다.(leaf에선 높이도 0이고 연산도 0번)따라서 bubbling down의 시간복잡도 = O(h) 이제 모든 h에 대해 계산하면$$ 시간복잡도 = O( \sum_{h=0}^{logN}\lceil{\frac{n}{2^{h..