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

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

 

Review

소수, 합성수, 서로소의 개념 알기.
집합 A가 연산 ⊗에 닫혀 있다라는 개념이해하기.
만약 집합 A의 원소 a,b가 각각 자연수일 때, a와 b가  연산 ⊗ 을 했을 때 자연수라면  집합 A는 닫혀있다라고 표현한다.
항등원, 역원의 개념 알기.

 

 

모듈러 (modular) 연산

 

합동의 개념

• 𝑎, 𝑏: 임의의 정수
• 𝑛 ≥ 2: 정수
• a ≡ b(mod n) ←→ n | (a - b) & n | (b-a) ←→  a, b를 n으로 나눈 나머지가 같다.

7 ≡ 2 (𝑚𝑜𝑑 5), −7 ≡ 3 (𝑚𝑜𝑑 5)

7 & 2는 법 5로 합동이다 ←→  7 is congruent to 2 modulo 5

 

설명을 하자면 7을 5로 나눈 나머지는 2이고 2를 5로 나눈 나머지는 2로 모듈러 합동이다.

또한 3을 5로 나눈 나머지는 3이고 -7을 5로 나눈 나머지도 3이다. 따라서 모듈러 합동이다.

 

➡️ 계산 방법 

 

정수처럼 연산하고 나중에 나머지만 계산

: 20 + 2 𝑚𝑜𝑑 5 = 22 = 2,

 7 × 3 𝑚𝑜𝑑 5 = 21 = 1

 

중간에 나머지로 바꾼 다음 계산해도 무방

20 + 2 𝑚𝑜𝑑 5 = 0 + 2 = 2

7 × 3 𝑚𝑜𝑑 5 = 2 × 3 = 6 = 1

 

→ 계산방법 같은 경우 5를 20으로 나눈 나머지와 2를 나눈 나머지를 더하는 것과 두 숫자를 다 더하고 나누는 값이 같고

( 중간에 나머지로 바꾼다음 계산하는 것 = 정수처럼 연산하고 나중에 나머지 계산하는 방법 )

 

합동의 성질은 다음과 같다.

• 𝑎 ≡ 𝑎 (𝑚𝑜𝑑 𝑛)
• 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛 이면 𝑏 ≡ 𝑎 𝑚𝑜𝑑 𝑛 
• 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛 이고 𝑐 ≡ 𝑑 𝑚𝑜𝑑 𝑛 이면 

• 𝑎 + 𝑐 ≡ 𝑏 + 𝑑 𝑚𝑜𝑑 𝑛
• 𝑎 − 𝑐 ≡ 𝑏 − 𝑑 𝑚𝑜𝑑 𝑛 
• 𝑎𝑐 ≡ 𝑏𝑑 𝑚𝑜𝑑 𝑛 

𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛 이고 𝑚|𝑛 이면 𝑎 ≡ 𝑏 (  𝑚𝑜𝑑 𝑚 )

 

 

합동 연산의 기본 성질은 다음과 같다.

 

기본적인 덧셈과 곱셈에 대한 연산 성질을 만족한다.

예를들어, 교환법칙 (덧셈, 곱셈)

• 𝑎  + 𝑏 = 𝑏 + 𝑎 (𝑚𝑜𝑑 𝑛)
• 𝑎 × 𝑏 = 𝑏 × 𝑎 (𝑚𝑜𝑑 𝑛)

 

결합법칙 (덧셈, 곱셈) 

• 𝑎 + 𝑏 + 𝑐 = 𝑎 + 𝑏 + 𝑐 (𝑚𝑜𝑑 𝑛)
• (𝑎 × 𝑏) × 𝑐 = 𝑎 × 𝑏 × 𝑐 (𝑚𝑜𝑑 𝑛)

 

분배법칙

• 𝑎 + 𝑏 × 𝑐 = 𝑎 × 𝑐 + 𝑏 × 𝑐 (𝑚𝑜𝑑 𝑛)
• 𝑐 × 𝑎 + 𝑏 = 𝑐 × 𝑎 + 𝑐 × 𝑏 (𝑚𝑜𝑑 𝑛)

 

항등원 & 역원

 

덧셈에 대한 항등원

• 0
• 𝑎 + 0 = 0 + 𝑎 = 𝑎 (𝑚𝑜𝑑 𝑛)
• 2 + 0 𝑚𝑜𝑑 5 = 2 (𝑚𝑜𝑑 5) 

덧셈에 대한 역원

• −𝑎
• 𝑎 + −𝑎 = −𝑎 + 𝑎 = 0
• 2 + −2 𝑚𝑜𝑑 5 = 2 + 3 = 0 𝑚𝑜𝑑 5

곱셈에 대한 항등원

• 1
• 𝑎 × 1 = 1 × 𝑎 = 𝑎 (𝑚𝑜𝑑 𝑛)
• 2 × 1 = 2 (𝑚𝑜𝑑 5)

곱셈에 대한 역원

 

• 곱셈에 대한 역원은 항상 존재하는 것은 아니다.

• 예를들어 𝑚𝑜𝑑 9 경우,

 

존재하는 경우

: 2 × 5 = 10 = 1 𝑚𝑜𝑑 9

: 5 = 2 −1 , 2 = 5 −1 𝑚𝑜𝑑 9

 

존재하지 않는 경우 

: 𝑚𝑜𝑑 9

6에 대해 역원이 존재하지 않음

 

𝑥를 역원이라고 하면, 6𝑥 = 9𝑚 + 1 

6𝑥 은 3의 배수, 9𝑚 + 1 은 3으로 나누었을 때 1이 남는 수 → 절대 같을 수 없다 → 역원 없음

 

 

곱셈에 대한 역원이 존재하기 위한 조건

 

GCD 정리

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

GCD(최대 공약수), LCM(최소 공배수) 구하기 (tistory.com)

GCD(최대 공약수), LCM(최소 공배수) 구하기

[ 참고 자료 ]

 

 

곱셈에 대한 역원 존재성

 

𝑎: 임의의 정수, 𝑛 ≥ 2: 자연수 일때,

𝑎가 𝑚𝑜𝑑 𝑛 으로 역원이 존재할 필요충분조건은 gcd 𝑎, 𝑛 = 1이다.

 

gcd 𝑎, 𝑛 = 1
𝑎 ⋅ 𝑠 + 𝑛 ⋅ 𝑡 = 1 인 두 정수 𝑠,𝑡 가 존재,
위 식의 양변에 𝑚𝑜𝑑 𝑛 을 취하면, 𝑎 ⋅ 𝑠 = 1 𝑚𝑜𝑑 𝑛 이다.
따라서 𝑎 ^−1 = 𝑠 𝑚𝑜𝑑 𝑛  이다.

 

곱셈에 대한 역원 구하기  ( 내가 가장 이해안되는 파트 )

 

예를 들어,  𝑎 = 1180, 𝑛 = 482 ⇒ gcd 𝑎, 𝑛 = 2 = 1180 ⋅ −29 + 482 ⋅ 71 의 풀이과정을 살펴보자.

1) 1180 = 2 × 482 + 216 • 216 = 1180 − 2 × 482

2) 482 = 2 × 216 + 50 50 = 482 − 2 × 216 = 482 − 2 × 1180 − 2 × 482 = −2 × 1180 + 5 × 482

3) 216 = 4 × 50 + 16 • 16 = 216 − 4 × 50 = 1180 − 2 × 482 − 4 × −2 × 1180 + 5 × 482 = 9 × 1180 − 22 × 482

4) 50 = 3 × 16 + 2 • 2 = 50 − 3 × 16 = −2 × 1180 + 5 × 482 − 3 × 9 × 1180 − 22 × 482 = −𝟐𝟗 × 𝟏𝟏𝟖𝟎 + 𝟕𝟏 × 𝟒𝟖𝟐

5) 16 = 8 × 2 + 0

⇒ 종료 & 앞 단계 결과 반환한다.

( 아직도 잘 이해가 되지 않는다.. 조금더 고민해봐야겠다.)

 

 

아래 블로그를 통해 추가학습을 진행할 예정이다.

[모듈러 역원] 나머지 연산의 곱셈의 역원 - NiklasJang’s Blog

[모듈러 역원] 나머지 연산의 곱셈의 역원

 

모듈러 연산과 1차 방정식

기본적으로 유리수에서 1차 방정식 풀이와 유사하다.

다만 모든 숫자에 대해 곱셈 역원이 존재하지 않음을 유의해야한다.

𝑎, 𝑐, 𝑑: 정수, 𝑛 ≥ 2 자연수 일때,
𝑎𝑥 + 𝑐 = 𝑑 (𝑚𝑜𝑑 𝑛) 에서 𝑥값 찾기 (1차 방정식 풀기)

𝑔𝑐𝑑 𝑎, 𝑛 = 1 인 경우만 𝑛으로 나눈 나머지 관점에서 유일한 𝑥 (0 ≤ 𝑥 ≤ 𝑛 − 1) 가 존재한다.

𝑔𝑐𝑑 𝑎, 𝑛 ≠ 1 이면 여러 해가 존재하거나 해가 존재하지 않는다.
6𝑥 = 5 (𝑚𝑜𝑑 9) → 해가 없음 • 6𝑥 = 3 𝑚𝑜𝑑 9 → 𝑥 = 2, 5, 8

 

 

잉여류 (Residue Class)

 

𝑚𝑜𝑑 5 로 다음은 다 같은 숫자

⋯ = −10 = −5 = 𝟎 = 5 = 10 = ⋯ = 5𝑘 (𝑚𝑜𝑑 5)

⋯ = −9 = −4 = 𝟏 = 6 = 11 = ⋯ = 5𝑘 + 1 (𝑚𝑜𝑑 5)

⋯ = −8 = −3 = 𝟐 = 7 = 12 = ⋯ = 5𝑘 + 2 (𝑚𝑜𝑑 5)

⋯ = −7 = −2 = 𝟑 = 8 = 13 = ⋯ = 5𝑘 + 3 (𝑚𝑜𝑑 5)

⋯ = −6 = −1 = 𝟒 = 9 = 14 = ⋯ = 5𝑘 + 4 (𝑚𝑜𝑑 5)

> 한마디로 다 같은 수를 다르게 표현한다는 의미인 것 같다.

 

잉여류란  “나머지들이 같은 숫자들의 집합” 을 뜻한다.

 

잉여류 표시방법

 

𝑚𝑜𝑑 𝑛 위에서 일반적으로 각 잉여류를 𝟎, 𝟏, 𝟐, … , 𝒏 − 𝟏 로 표시 

엄밀하게는 숫자 자체와 혼동을 피하기 위해 0 bar, … , 𝑛 − 1 bar 로 표시

modulo 𝑛 표현이라는 것에 혼동의 여지가 없으면, 보통 숫자위의 bar를 생략하여 표시

 

 

잉여류 연산과 완전 잉여계 𝒁𝒏

 

모듈러 연산에 따라 잉여류 간 연산이 자연스럽게 정의되었다.

• 잉여류 𝑎, 𝑏에 대해, 𝑎 + 𝑏 𝑚𝑜𝑑 𝑛 & 𝑎𝑏 (𝑚𝑜𝑑 𝑛)

즉, 0,1,2, … , 𝑛 − 1 만으로 구성된 숫자 집합에 대해 𝑚𝑜𝑑 𝑛 연산

• 덧셈, 곱셈이 잘 정의됨
• 덧셈에 대한 항등원 0 이다.
• 덧셈에 대한 역원 −𝑎 𝑚𝑜𝑑 𝑛 이다.
• 곱셈에 대한 항등원 1이다.
• 곱셈에 대한 역원 존재
• 숫자에 따라 존재할 수도 존재하지 않을 수도 있기는 하다.

완전 잉여계 (Complete Residue System)

• 𝑚𝑜𝑑 𝑛 에 대해 0,1,2, … , 𝑛 − 1 을 일컬는다.
• 𝒁𝒏으로 표기한다.

기약 잉여계 𝒁*𝒏

• 𝑍𝑛 = 0,1, … , 𝑛 − 1
• 곱셈에 대한 역원이 존재하는 수도 있고, 존재하지 않는 수도 있다.
• 𝑍𝑛의 원소 중에서 곱셈에 대한 역원이 존재하는 숫자들의 집합이다.
• 𝑍*𝑛  은 𝑍𝑛 의 부분집합이다.

곱셈에 대한 역원
𝑎: 임의의 정수, 𝑛 ≥ 2: 자연수 일때,
𝑎가 𝑚𝑜𝑑 𝑛 으로 역원이 존재할 필요충분조건은 gcd 𝑎, 𝑛 = 1이다.

• 𝑍*𝑛 는 0,1, … , 𝑛 − 1 중에서 𝑛 과 서로소인 숫자의 집합이다.
• 𝑍10 = 0,1,2,3,4,5,6,7,8,9 ⇒ 𝑍*10 = 1,3,7,9
• 𝑍15 = 0,1,2,3,4,5,6,7,8,9,11,12,13,14 ⇒ 𝑍*15 = {1,2,4,7,8,11,13,14}

𝒁*𝒏  원소의 개수

 

- 오일러 𝜙 함수

• 자연수 𝑛
• 𝜙 𝑛 = “𝑛 이하의 자연수 중 𝑛 과 서로소인 자연수의 개수”

- 정의에 의해, 𝑍*𝑛의 원소의 수 = 𝜙(𝑛)

- 𝑝 소수

• 1, … , 𝑝 − 1 이 모두 𝑝 와 서로소 이다.
• 𝜙 𝑝 = 𝑝 − 1 

- 𝜙 𝑛 계산하기

• 자연수 𝑛에 대한 소인수분해 𝑛 = 𝑝1 𝑘1 ⋅ 𝑝2 𝑘2 ⋯ 𝑝ℓ 𝑘ℓ를 계산한다.
• 𝜙 𝑛 = 𝑝1 𝑘1−1 (𝑝1 − 1) ⋅ 𝑝2 𝑘2−1 (𝑝2 − 1) ⋯ 𝑝ℓ 𝑘ℓ−1 (𝑝ℓ − 1)
• 𝑍15 = 0,1,2,3,4,5,6,7,8,9,11,12,13,14 ⇒ 𝑍15 ∗ = {1,2,4,7,8,11,13,14} • 𝑍15 ∗ 원소 개수 = 8
• 15 = 3 ⋅ 5 ⇒ 𝜙 15 = 3 − 1 ⋅ (5 − 1) = 8

 

특수한 완전 잉여계 𝒁𝒑

 

소수 𝑝 는 특이한 기약 잉여계를 정의한다.

 

𝑍𝑝 = 0,1, … , 𝑝 − 1

소수 𝑝는 1, … , 𝑝 − 1 과 모두 서로소이다.

< 소수의 정의, “자기자신과 1만을 약수로 가진다” >

따라서, 𝑍*𝑝 는 𝑍𝑝에서 0을 제외한 모든 수와 같다.

𝑍*𝑝 = 1, … , 𝑝 − 1

𝑍𝑝 는 덧셈에 대한 항등원 0을 제외하고 모든 숫자가 곱셈에 대한 역원을 가진다.

유리수, 실수와 비슷한 성질을 가지고 있다고 할 수 있다.

 

( 수업을 제대로 안들었는지 이해가 안가는 부분이다. 다시 정리가 필요하다. )

 

 

 

✅해당 내용은 참고용이다.

 

 

페르마의 작은 정리

 

페르마의 작은 정리 (Fermat’s Little Theorem) 란?

𝑝: 소수 
𝑎: 𝑝 와 서로소인 임의의 정수 𝑎 𝑝−1 = 1 ( 𝑚𝑜𝑑 𝑝 )

 

오일러의 정리

 

오일러의 정리 (Euler’s Theorem) 란?

𝑛: 자연수
𝑎: 𝑛 과 서로소인 임의의 정수 𝑎^ 𝜙(𝑛) = 1 (𝑚𝑜𝑑 𝑛)