1.1.1. 2.1 정수론 ¶
- p.24
- 암호학에서는 정수론과 유한체 이론이 많이 사용되고 있다.
- 정수론이 쓰이는건 알았는데, 유한체를 여기서 볼 줄은 몰랐네 - 김도엽
- 정수론이 쓰이는건 알았는데, 유한체를 여기서 볼 줄은 몰랐네 - 김도엽
- 이와 같이 b는 a로 나누어 떨어진다고 말하는 관계를 다음과 같이 표시한다.
a|b
- a|b를 외울 때 "a can divide b"라고 외우면 될 듯 (밑에 링크는 "a divides b"라고 설명하고 있긴 함) - 김도엽
- Meaning of a|b or a pipe b
- a|b를 외울 때 "a can divide b"라고 외우면 될 듯 (밑에 링크는 "a divides b"라고 설명하고 있긴 함) - 김도엽
- 암호학에서는 정수론과 유한체 이론이 많이 사용되고 있다.
- p.25
- 임의의 정수 a가 있을 때 이 수는 다음과 같이 소수의 곱으로 유일하게 표시할 수 있다.
- 모든 수는 소수의 곱으로 이루어짐을 a=p1^(e1)*p2^(e2)*...*pr^(er)와 같이 수식으로 나타냈구나 - 창민규
- 모든 수는 소수의 곱으로 이루어짐을 a=p1^(e1)*p2^(e2)*...*pr^(er)와 같이 수식으로 나타냈구나 - 창민규
- 임의의 정수 a가 있을 때 이 수는 다음과 같이 소수의 곱으로 유일하게 표시할 수 있다.
- p.26
- 이 때, 원소의 개수 ϕ(m)을 Euler의 ϕ함수 (ϕ-function) 혹은 Euler의 토션 함수(totient function)라고 한다.
- 파이 함수를 토션 함수라고도 부르는 구나 - 창민규
- 파이 함수를 토션 함수라고도 부르는 구나 - 창민규
- 이 때, 원소의 개수 ϕ(m)을 Euler의 ϕ함수 (ϕ-function) 혹은 Euler의 토션 함수(totient function)라고 한다.
- p.27
- 만약 소수 p가 있고 정수 a가 p로 나누어지지 않는 수라면 다음과 같은 방법으로 a의 역수를 구할 수 있다
- a^(p-1)을 a^(-1)*a^(p-2)로 나눠서 a^(-1)을 구하려는 거구나 - 창민규
- a^(p-1)을 a^(-1)*a^(p-2)로 나눠서 a^(-1)을 구하려는 거구나 - 창민규
- 만약 소수 p가 있고 정수 a가 p로 나누어지지 않는 수라면 다음과 같은 방법으로 a의 역수를 구할 수 있다
1.1.2. 2.2 유한체 ¶
- p.28
- 따라서 덧셈군일 때는 항등원은 '0'(영원)으로 표시하고 승산군일 때의 항등원은 '1'(단위원)으로 표시한다.
- 승산원은 곱셈군을 의미하는건가?... - 창민규
- 승산원은 곱셈군을 의미하는건가?... - 창민규
- 따라서 덧셈군일 때는 항등원은 '0'(영원)으로 표시하고 승산군일 때의 항등원은 '1'(단위원)으로 표시한다.
- p.29
- 특히, 곱셈에 대한 단위원이 존재하고 영이 아닌 원소가 승산에 대하여 역원을 갖는 가환환을 체(field) F라고 정의한다.
- 그러면 결국 "체" F 정의는 {{①닫힘 ②결합 법칙 ③항등원 ④역원} 성질을 가지는 ⑤가환군이면서 ⑥곱셈에 대한 닫힘 ⑦곱셈에 대한 결합법칙 ⑧분배법칙} 성질과 ⑨곱셈의 역원을 가지는 ⑩가환환 이라고 할 수 있는게 맞나? - 김도엽
- 그러면 결국 "체" F 정의는 {{①닫힘 ②결합 법칙 ③항등원 ④역원} 성질을 가지는 ⑤가환군이면서 ⑥곱셈에 대한 닫힘 ⑦곱셈에 대한 결합법칙 ⑧분배법칙} 성질과 ⑨곱셈의 역원을 가지는 ⑩가환환 이라고 할 수 있는게 맞나? - 김도엽
- 특히, 곱셈에 대한 단위원이 존재하고 영이 아닌 원소가 승산에 대하여 역원을 갖는 가환환을 체(field) F라고 정의한다.
- p.34
- 유클리드 알고리즘을 이용한 최대 공약수를 구하는 방법은 어떠한 음이 아닌 정수 a와 그보다 작은 정수 b가 있을 때 다음 등식에 기반한다.
gcd(a, b)=gcd(b, a mod b)
- C-style로 한 줄 코딩할 수 있음. 이걸로 gcd는 물론 lcm 구해야 할 때도 유용하게 써먹음. - 김도엽
int gcd(int a, int b) { return b ? a : gcd(b, a%b); }
- C-style로 한 줄 코딩할 수 있음. 이걸로 gcd는 물론 lcm 구해야 할 때도 유용하게 써먹음. - 김도엽
- 유클리드 알고리즘을 이용한 최대 공약수를 구하는 방법은 어떠한 음이 아닌 정수 a와 그보다 작은 정수 b가 있을 때 다음 등식에 기반한다.
- p.34
- 그런데 유클리드 알고리즘을 확장한 확장 유클리드 알고리즘은 두 개의 정수가 서로 소인 경우에 한 수에 대한 다른 수의 곱셈에 대한 역원을 계산하는데 사용된다
- 유클리드 알고리즘에서의 ax+by=gcd(a,b)와 모듈러를 이용하여 역원을 구하겠구나 - 창민규
- 유클리드 알고리즘에서의 ax+by=gcd(a,b)와 모듈러를 이용하여 역원을 구하겠구나 - 창민규
- 그런데 유클리드 알고리즘을 확장한 확장 유클리드 알고리즘은 두 개의 정수가 서로 소인 경우에 한 수에 대한 다른 수의 곱셈에 대한 역원을 계산하는데 사용된다
- p.35
- 만약 두 정수 f와 f보다 작은 정수 d가 서로 소이면, 즉 gcd(f, d)=1이라면, 그때 d는 모듈러 f상에서 곱셈에 대한 역원을 갖는다. 즉, d·d^-1=1 mod f인 d^-1
- RSA 키 만드는 과정중 비밀키 d를 만들때, ϕ(N)상에서 e의 곱셈에 대한 역원으로 d를 결정해야 함. 마침 ed≡1(mod ϕ(N))에서 이미 e를 ϕ(N)와 서로소인 정수로 결정했기 때문에 e의 곱셈에 대한 역원이 존재하므로 d를 구할 수 있는 것임. - 김도엽
- RSA 키 만드는 과정중 비밀키 d를 만들때, ϕ(N)상에서 e의 곱셈에 대한 역원으로 d를 결정해야 함. 마침 ed≡1(mod ϕ(N))에서 이미 e를 ϕ(N)와 서로소인 정수로 결정했기 때문에 e의 곱셈에 대한 역원이 존재하므로 d를 구할 수 있는 것임. - 김도엽
- 만약 두 정수 f와 f보다 작은 정수 d가 서로 소이면, 즉 gcd(f, d)=1이라면, 그때 d는 모듈러 f상에서 곱셈에 대한 역원을 갖는다. 즉, d·d^-1=1 mod f인 d^-1
