[현대암호학] 제 2장 수학적 배경 (2)

(2021.07.25)

 

3주차 암호 스터디 (43쪽~61쪽)

---

 

2.6 중국인의 잉여 정리와 Euler의 φ함수

2.6.1 중국인의 잉여 정리

양의 정수 m1,m2,m3,...,mn이 쌍마다 서로소일 때, 연립일차 합동식
x≡b1 mod m1
x≡b2 mod m2
...
x≡bn mod mn   은
법 m=m1·m2·m3·...·mn 에 대해 단하나의 해를 가진다.


Mi=m/mi (i=1,2,...,n) 으로 놓으면
m=Mi·mi, gcd(mi,Mi)=1  이므로
Mi·Ni≡1 mod mi  가 성립하는 Ni가 존재한다. 
이때, T=∑bi·Mi·Ni (시그마 i=1부터 i=n까지) 라고 놓으면 
모든 i=1,2,...,n 에 대하여  T=b1·M1·N1+b2·M2·N2+...+bn·Mn·Nn ≡bi·Mi·Ni mod mi 가 되므로
x≡T mod m 은 연립 1차 합동식의 유일한 해가 된다.

 

예제) 다음 연립 1차 합동식의 해를 구하여라.

x≡4 mod 5

x≡3 mod 7

x≡6 mod 11

 

풀이)

m=m1·m2·m3=5·7·11=385

M1=m2·m3=7·11=77

M2=m1·m3=5·11=55

M3=m1·m2=5·7=35

 

M1,M2,M3의 승산역원을 구해보면,

M1=77≡2 mod 5     --> 5=2x2+1   --> 5x1-2x2=1    --->N1=3

M2=55≡6 mod 7     --> 7=6x1+1   --> 7x1-6x1=1    --->N2=6

M3=35≡2 mod 11   --> 11=2x5+1  --> 11x1-2x5=1  --->N3=6

 

T=b1·M1·N1+b2·M2·N2+...+bn·Mn·Nn ≡bi·Mi·Ni mod mi 

T=4x77x3+3x55x6+6x35x6 mod 385

T≡94 mod 385

 

 

 

 

2.6.2 Euler의 φ함수

정수 01,2,3,...,m-1 에서 m과 서로소인 수를 x, 그 개수를 φ(m)으로 표시한다.

p가 소수일 때, 
φ(p)=p-1 이 된다.
φ(p^e)=p^e-p^(e-1) 이 된다.

1부터 p^e 까지의 정수 가운데 p^e와 서로소가 아닌것(p로 나누어지는 것)은 
1xp, 2xp, ... , p^(e-1)xp 로 p^(e-1)개가 있기 때문에 φ(p^e)=p^e-p^(e-1)가 성립한다.

일반적으로 φ(m)은 p,q,r,...이 소수이고 m=p^a·q^b·r^c... 일 때, 
φ(m)=m(1-1/p)(1-1/q)(1-1/r)... 이 성립한다.

 

 

 

 

 

 

2.7 이차 잉여

정수 m을 법으로 하는 이차 합동식 x^2≡a mod m이 
해를 가질 때, a를 법 m에 대한 이차 잉여라고 한다. (quadratic residue modulom)
해를 가지지 않을 때, a를 법 m에 대한 이차 비잉여라고 한다. (quadratic nonresidue modulom)

Euler의 정리에 의하면 p가 소수로 gcd(a,p)=1 일 때,
a가 법 p에 관한 이차 잉여이면, a^{(p-1)/2}≡1mod p
a가 법 p에 관한 이차 비잉여이면, a^{(p-1)/2}≡-1 mod p

a가 법 p에 관한 이차 잉여이면, 2차 합동식  x^2≡a mod p 은
두개의 해 x≡x0 mod p, x≡-x0 mod p 를 갖는다.

법 p의 p가 홀수인 소수이고, gcd(a,p)=1 일 때, 이차 합동식의 존재성을 판정하기 위해
(a/p)=(a^{(p-1)/2})= 1 : x^2≡a mod p 의 해 존재
                          -1 : x^2≡a mod p 의 해 없음
라고 정의하고, Legendre 기호라고 한다.

따라서, a≡b mod p 이면 (a/p)≡(b/p) 이다.