[정수론](15)[이차잉여]

제곱수의 합동 성질임의의 b에 대해b^2 ≡ (m-b)^2 (mod m)증명(m-b)^2 ≡ m^2 -2mb + b^2 ≡ 0 + 0 + b^2 (mod m)따라서 b^2 ≡ (m-b)^2 (mod m)즉, 제곱수의 합동을 계산하려면 대충 반절까지만 보면 된다.m = 홀수: 1~(p-1)/2 까지 보고 이후는 대칭m = 짝수: 1~p/2 까지 보고 p/2 기준으로 대칭 이차잉여이차잉여(QR): mod p에 대해 어떤 제곱수와 합동인 수 즉, 어떤 b가 존재하여 a ≡ b^2 (mod p)라면 a는 p의 이차잉여이다.이차비잉여(NR): mod p에 대해 어떤 제곱수와 합동이 아닌 수 즉, a ≡ b^2 (mod p)인 b가 존재하지 않는다면 a는 p의 이차비잉여이다.0은 QR도 NR도 아니다.예..

[정수론](14)[소수의 성질과 라빈-밀러 판정법]

소수의 성질적당한 소수 p, 홀수 q에 대해p - 1 = 2^k*q 꼴이라면 p∤a인 임의의 수 a에 대해 적어도 1개가 참이다.a^q ≡ 1 (mod p)a^q, a^2q, a^3q, ..., a^(2^(k-1)*q) 중 1개는 mod p에서 -1과 합동증명페르마의 소정리에 의해 a^p-1 ≡ 1 (mod p)따라서 a^(2^k*q) ≡ 1 (mod p)case 1: a^q ≡ 1 (mod p) 이라면?a^q(2^k) ≡ 1^(2^k) ≡ 1 (mod p)이므로 만족한다.case 2: a^q !≡ 1 (mod p) 이라면?a^(2^k*q) ≡ 1 (mod p) 이므로a^q, a^2q, a^3q, ..., a^(2^(k-1)*q) 중 제일 마지막 수가 1과 합동이다.따라서 제곱하면 1과 합동이 되는 수 ..

[정수론](13)[소수 판정과 카미이클 수]

소수의 판정법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 = 홀수모든 카마이클 수는 서로 다른 소수의 곱이다소수 p..

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이므로 ..