1주차_현대암호학 기초 < 기초 정수론 >

1. 정수와 나눗셈 
2. 소수와 소인수분해 
3. 모듈러 연산 & 합동 
4. 𝑍𝑛 & 𝑍𝑛

 

[ 암호와 대수적 구조 ]

이 단원 [ 학습 목표 ] 는

• 정수와 소수의 성질에 대해 이해한다. 
• 합동의 정의와 모듈러 연산을 이해한다.
• 잉여계(𝑍𝑛, 𝑍𝑛 ∗ )의 개념과 연산을 이해한다.

이다.

 

 

1. 정수와 나눗셈 

 

✅ 숫자 집합

표기	집합
R	실수 집합
Z	정수 집합
N	자연수 집합

➡️ 소수 (prime)

약수가 1과 자기자신만 있는 2보다 크거나 같은 수 

ex) 2, 3, 5, 7, …

 

➡️ 합성수 (composite)

소수가 아닌 2보다 크거나 같은 수 

ex) 4, 6, 8, 9, …

 

➡️ 서로소 (Relatively prime)

두 정수 𝑎, 𝑏가 “서로소 (relatively prime) 이다

ex) 5 & 6 • 9 & 14

 

➡️ 집합 𝐴가 연산 ⊗ 에 닫혀 있다.

모든 𝐴의 원소 𝑎, 𝑏 에 대해, 𝑎 ⊗ 𝑏도 𝐴의 원소이다.

 

➡️ 항등원 (identity)

연산 ⊗ 에 대해 집합 𝐴의 원소 𝑒가 항등원이다.

➡️ 역원 (inverse) 

연산 ⊗ 에 대해 𝐴의 원소 𝑏가 𝐴의 원소 𝑎의 역원이다.

집합	덧셈	덧셈 항등원	덧셈 역원	곱셈	곱셉 항등원	곱셈 역원
자연수	닫혀 있다	없다	없다	닫혀 있다	1	없다
정수	닫혀 있다	0	-a	닫혀 있다	1	없다
실수	닫혀 있다	0	-a	닫혀 있다	1	1/a

닫혀있다라는 건 어떠한 집합 S의 모든 원소들이 조건을 만족시켰을 때를 말한다.

<즉, 하나라도 만족하지 않을 시 닫혀있지 않다.>

 

 

[ 나눗셈 정리 ]

➡️ 나눗셈 정리

• 𝑎, 𝑏: 임의의 정수, 𝑏 ≠ 0 
• 다음을 만족시키는 정수 𝑞 (몫), 𝑟 (나머지) 이 유일하게 존재한다 
• 𝑎 = 𝑏𝑞 + 𝑟
• 0 ≤ 𝑟 < |𝑏|

• 𝑎 = 7, 𝑏 = 3 ⇒ 7 = 3 × 2 + 1

• 𝑎 = 7, 𝑏 = −3 ⇒ 7 = −3 × −2 + 1

• 𝑎 = −7, 𝑏 = −3 ⇒ −7 = −3 × 3 + 2

 

* 나머지는 양의 정수여야한다.

 

[ 약수와 배수 ]

약수와 배수에 관한 성질 정수 𝑎, 𝑏, 𝑐, 𝑑 에 대해 아래가 성립한다.

1. ±1|𝑎, 𝑎| ± 𝑎, 𝑎|0
2. 𝑎|1 이면 𝑎 = ±1 이다.
3. 𝑎|𝑏 이고 𝑏|𝑐 이면 𝑎|𝑐 이다.
4. 𝑎|𝑏 이고 𝑐|𝑑 이면 𝑎𝑐|𝑏𝑑 이다.
5. 𝑎|𝑏 이고 𝑏|𝑎 이면 𝑎 = ±𝑏 이다.
6. 𝑎|𝑏 이고 𝑏 ≠ 0 이면 𝑎 ≤ |𝑏| 이다.
7. 𝑎|𝑏 이고 𝑎|𝑐 이면 임의의 정수 𝑥와 𝑦에 대해 𝑎|(𝑏𝑥 + 𝑐𝑦) 이다.

 

[ 최대공약수 ]

  

• 양의 정수 𝑐 가 두 정수 𝑎 와 𝑏 의 최대공약수
• (공약수) 𝑐 | 𝑎 이고 𝑐 | 𝑏 
• (최대) 𝑎 와 𝑏 의 모든 공약수 중 최대 
• (표기) 𝑐 = gcd(𝑎, 𝑏)

GCD 정리
• 𝑎, 𝑛: 임의의 정수 & 𝑑 = gcd(𝑎, 𝑛)
⇒ 1) 𝑎𝑠 + 𝑛𝑡 = 𝑑 를 만족시키는 두 정수 𝑠, 𝑡 가 존재한다. (단, 유일하지는 않음)
    2) 𝑎, 𝑛 을 위와 같은 방식으로 결합했을 때 gcd(𝑎, 𝑛) 이 얻을 수 있는 최소의 자연수이다.
    (즉, 임의의 두 정수 𝑠 ′ ,𝑡′ 에 대해 |𝑎𝑠 ′ + 𝑛𝑡 ′ | ≥ 𝑑)

 예시 )

  • 𝑎 = 6, 𝑛 = 9 ⇒ gcd 𝑎, 𝑛 = 3 = 6 ⋅ −1 + 9 ⋅ 1

  • 𝑎 = 1180, 𝑛 = 482 ⇒ gcd 𝑎, 𝑛 = 2 = 1180 ⋅ −29 + 482 ⋅ 71

 

------> 추가학습하기

 

 

[ 소수와 소인수 분해 ]

 

소수에 대한 기본적인 사실

 

소수 (prime)

• 약수가 1과 자기자신만 있는 2보다 크거나 같은 수를 뜻한다.

정리

• 𝑝가 소수이고 𝑎, 𝑏 는 정수라고 하자. 𝑝|𝑎𝑏 이면 𝑝|𝑎 또는 𝑝|𝑏 이다
• 𝑝가 소수이고 𝑎1, 𝑎2 … 𝑎𝑛 이 정수라고 하자.
  𝑝|(𝑎1 ⋅ 𝑎2 ⋯ 𝑎𝑛) 이면 어떤 수 𝑎𝑖에 대해 𝑝|𝑎𝑖 이다

 

소인수 분해정리

 

정리

• 1을 제외한 모든 양의 정수는 소수들의 곱으로 표시되며 그 표시 방법은 (곱하는 순서를 무시하면) 유일하다.

• 소수 𝑝는 그 자체를 하나의 소수의 곱으로 간주한다.

• 소인수 분해

• 1을 제외한 양의 정수 𝑛을 소수들의 곱으로 표시한 것
•  3
•  12 = 2 2 × 3
•  25 = 5 2

 

소수의 무한성

정리

• 소수는 무한히 많다.