소수의 판정법root(n)보다 작거나 같은 소수로 나누기페르마의 소정리 -> 카마이클 수라는 반례가 있음! 카마이클 수합성수지만 페르마의 소정리를 만족하는 수gcd(a, m) = 1일때a^n ≡ a (mod n) 인 합성수 n 코어젤트의 카마이클 수 판정법n이 합성수라 가정할 때 n = 홀수 n을 나누는 모든 소수 p에 대해 p^2 ∤ n p-1 | n-1 이라면 n은 카마이클 수이다. 증명 모든 카마이클 수는 홀수이다모든 a에 대해 a^n ≡ a (mod n)을 만족해야 한다.a = n-1이라 가정할 때 n-1 ≡ -1 (mod n) 이므로,따라서 (n-1)^n ≡ (-1)^n ≡ 1 (mod p)따라서 n = 홀수 모든 카마이클 수는 서로 다른 소수의 곱이..

1. 관찰로 규칙성 찾기그냥 맨바닥 부터 시작하니까 규칙이 감이 안 잡히는데일단 작은 수에 대해서 몇개만 (p로 표현된 식)에 p를 넣어보자.짝수인지 홀수인지, 몇의 배수인지 보는 게 좋다.이때 edge case로 2를 조심해야 한다.2. mod로 정수 집합 분할하기일단 edge case인 2를 처리했다면 mod로 정수들의 집합을 나눠보자.(집합론에선 동치관계가 분할을 형성한다고 배운다.따라서 mod m에 대해 0~m-1에 있는 각각의 case 모음집의 합은 정수 집합과 같다.)2를 제외한 p는 모두 홀수이므로 만약 mod 3에 대해 분할하면p = 3k+1 or 3k+2 or 3 꼴이다.그 다음 각각의 경우에 대해 합성수인지 소수인지 판별하면 된다. 예) 소수 p가 5 이상일 때 p^2+2가 합성수임을 ..

암호학 둘러보기 9 참고(여기서 더 정수론 내용이 들어갔다.)과정메세지 보내는 A, 메세지 받는 B이고 공개된 파라미터 e가 있다.B의 공개키(N): N = p*q (p, q는 매우 큰 소수)B의 개인키([d]): [d]*e = 1 (mod[p-1]*[q-1]) (모듈러 역원 구하기. 만족하는 정수 d는 1개밖에 없으니 안심)A가 보낼 메세지 암호화(C): C = M^e (mod N)B는 자신의 개인키로 복호화(M): M = C^[d] (mod N)내가 암호학 둘러보기에선 이렇게 써놨다.이처럼 RSA는 상대의 공개키로 보낼 메세지를 암호화한다.이제 정수론적으로 다시 봐보자.과정매우 큰 소수 p, q를 선택하고 m = pq라고 두자p, q는 소수이므로 ϕ(m) = (p-1)(q-1)이후 ϕ(m)와 서로소인..

연속제곱법: a^k (mod m) 빨리 계산하기k를 2의 거듭제곱의 합으로 표현k = u0*A0 + u1*A1 +...+ ur*Ar각각의 제곱들을 mod 연산하기a ≡ A0 (mod m)a^2 ≡ A1 (mod m)a^4 ≡ A2 (mod m)a^8 ≡ A3 (mod m)...a^r ≡ Ar (mod m)구한 A들을 가지고 연산하기A0^u0*A1^u1*...*Ar^ur ≡ a^(u02^0 + u12^1 + ... ur2^r) ≡ a^k (mod m) 법 m에 대한 k제곱근 구하기x^k ≡ b (mod m)에서gcd(b, m)=1, gcd(k, ϕ(m)) = 1이라면ϕ(m) 계산하기ku-ϕ(m)v = 1인 양의 정수 u, v를 구함b^u를 연속제곱법으로 계산x ≡ b^u (mod m)증명x^(ku) ≡ x..

임의의 원시 피타고라스 세 수 (a, b, c)가 있다. 이때 다음을 보여라a or b가 3의 배수인가?언제 a, b, c가 5의 배수인가?a or b가 3의 배수인가?정수 집합을 mod 3의 동치관계로 분할해보자.즉, a, b, c = 3k, 3k+1, 3k+2 꼴이다. (k=정수)만약 a, b 모두 3의 배수가 아니라면?a, b = 3k+1 or 3k+2 꼴이다.a^2 + b^2 = c^2에서 mod 3을 보기 위해 (3k+1)^2, (3k+2)^2에 대한 mod 3을 봐보자.(3k+1)^2 ≡ 3(3k^2+2k)+1 ≡ 1 (mod 3)(3k+2)^2 ≡ 3(3k^2+4k+1)+1 ≡ 1 (mod 3)따라서 a^2+b^2 ≡ 2 (mod 3)일 수밖에 없다.그러나, c가 될 수 있는 3k, 3k+1..

무한소수정리소수는 무한히 많다증명만약 소수가 유한하고 유한개의 소수 집합 R = {p1, p2, ..., pr}이 있다 가정A = p1*p2*...*pr + 1이라는 수를 잡으면만약 A = 소수?A는 R에 없는 소수이므로 모순 발생만약 A = 합성수?소수의 가약성에 의헤 A는 소수의 곱으로 표현 가능하다.이때 A를 나누는 가장 작은 소수를 q라 한다면 만약 q = pi라면 q|pi, q|A => q|1이어야 하는데 불가능 따라서 q != pi이걸 모든 p에 대해 반복한다면 모든 p가 q와 다른 수라는 걸 알 수 있다.따라서 q는 R에 없는 새로운 수 이므로 모순 발생디리클레의 등차수열 정리gcd(a, m) = 1인 정수 a, m이 있을 때, p ≡ a (mod m)인 소수 p가 무한히 많다...

p ≡ 5 (mod 6) 꼴의 소수가 무한함을 보여라.p = 6k + 5꼴의 소수가 유한하다 가정하자.그리고 이 꼴의 모든 소수를 모은 집합 R을 정의한다.R = {p | p = 6k+5, p=소수, k=정수} = {5, p1, p2, ..., pr}그리고 어떤 수 A = 6*(p1*p2*...*pr) + 5라고 정의한다. A = 소수?A는 R에 없는 새로운 6k+5꼴의 소수이므로R이 모든 6k+5꼴의 모음이라는 가정에 모순됨 A = 합성수?산술의 기본정리에 의해 A는 소수들의 곱으로 나타낼 수 있다.A = 6*(p1*p2*...*pr) + 5 = q1*q2*...*qs여기서 소수 q와 합동일 수 있는 것들을 찾아보자. q ≡ 0 (mod 6) -> q=6k 꼴이므로 소수가 아니라 안됨 q ≡ ..

정수론 수업을 듣고 흥미로운 문제를 들었다.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..