베루의 보안공부

이차잉여란 해(근)를 가질 때, 정수 a을 법 m이며, 해(근)를 가지지 않을 때 정수 a을 법 m으로 한 이차비잉여 라고 한다.

이차잉여에서 집합 Z_m* 의 원소를 제곱해서 갑을 구할 수 있다.

이를 계산하기 위해선 오일러의 판정기준이 있다 

홀수인 소수 p와 (a, p) = 1인 정수 a에 대하여 성립한다.

Ⅰ) 정수 a가 이차잉여일 때 필요충분조건은 a^ p-1/2 ≡ 1(mod p)이다.

이때, 합동식 x^2 ≡ a (mod p)에서 꼭 두 개의 해를 가진다.

Ⅱ) 정수 a가 이차비잉여일 때 필요충분조건은 a^ p-1/2 ≡ -1(mod p)이다.

이차비잉여에서 필요충분조건이란 홀수인 소수를 뜻한다.

이때, 합동식 x^2 ≡ a (mod p)에서 해가 존재하지 않는다.

※이차잉여를 계산할 때 기약잉여계를 바탕으로 계산해야한다.

원시근을 하기에 앞서 먼저 배워야 할 것은 위수(order)이다.

(a, m) = 1이 성립되고  a^r ≡ 1 (mod m)을 만족하는 정수 중에서 가장 작은 양의 정수 r(나머지)을 법 m, p에 관한 a의 위수이다.

예시로 들자면 법 7에 관한 2의 위수를 구하여라

2^r ≡ 1(mod 7)을 만족하는 가장 작은 양의 정수 r을 구할 때 2^1 ≡ 1(mod 7), 2^2 ≡ 4 (mod 7),  2^3 ≡  1(mod 7)

법 7에 관한 2의 위수는 3 ≤ ∂(7) = 6이다. 즉 ord_7 2 = 3이다. 

법 7에 관한 3의 위수에서 3^r ≡ 1(mod 7)일 때 3^1 ≡  3 (mod 7), 3^2 ≡  2 (mod 7), 3^3 ≡  6 (mod 7), 3^4 ≡  4 (mod 7), 3^5 ≡  5 (mod 7), 3^6 ≡  1 (mod 7)이며 법 7에 관한 3의 위수는 r = 6이다.  

위수:ord_7 3 = 6인 것이다.

※계산할 때 오일러 피 함수로 모듈러 m, p를 먼저 구하고 나온 값 만큼 거듭제곱을 해야한다. (1 ~ m-1 까지)

n | ∂(m) 은 약수배수 관계이다. 또한 ∂(m)은 원소의 개수와 같다.

원시근과 위수는 꽤나 비슷하다. ord_m a =  ∂(m) 동일한 값이 나오면 원시근, ord_m a 일 때 위수인 것이다.

원시근은 2, 4, p^k, 2p^k만 존재하고 그 이상에 합성수는 존재하지 않는다. 

값이 있더라도 그 값은 해가 될 수 없다.

존재하는 경우는 집합 Z^* p인 기약잉여계 즉 소수일 때만 존재한다.

오일러 함수에 설멍하자면 완전잉여계, 기약잉여계를 사용할 때 Zm, Zp에 대한 값으로 해당 식에 답이 몇 개 존재하는지 판별할 수 있는 함수이다.

∂(m)  = |Z* m|이랑 동일하다.

m이 거듭제곱, 소수, 합성수일 때 오일러 함수를 계산할 때 식이 달라진다.

한 자리 소수일 경우: ∂(m)  = m-1 

합성수 일 경우: ∂(m) = (m-1) x (n-1)  

거듭제곱 일 경우= m^2 - m^1 

와 같이 계산하면 된다.

예시를 보여주면  ∂(3)  = 3-1  = 2,  ∂(6) = (3-1) x (2-1) = 2 x 1 = 2 , ∂(9) = (3^2) - (3^1) = 9 - 3 = 6 과 같다.

 값이 클 경우는 어떻게 계산하나요?

소인수분해 했을 때 나왔던 값만 넣어주면 되며 이 식에는 지수가 들어가지 않는다.

페르마 정리는 a^ ∂(p) ≡ 1 (mod p) 또는 a^p-1 ≡ 1 (mod p)라는 점이다. (첫번째 버전)

어떠한 양의 정수가 소수인가를 판정하는데 필요한 정리이다.

두번째 버전에선 a^p ≡ a (mod p)를 만족한다고 해서 p가 반드시 소수는 아니하다.  

일차합동식은 일차방정식과 같은 형태지만 합동식이 들어가 있어 일차합동식이라 부른다.

식으로 표현하자면 ax+ b ≡ 0 (mod ⁡m)에 형태이다.

일차방정식이 있듯이 이차방정식이 있고 당연히 이차합동식 또한 존재한다.

x^2 + 1 ≡ 0 (mod 5)일 때  , f(x) = x^2 + 1 ≡ 0 (mod 5)

f(0) = 1 ≡ 1 (mod 5) ,  f(1) = 2 ≡ 2 (mod 5), f(2) = 5 ≡ 0 (mod 5)

f(3) = 10 ≡ 0 (mod 5), f(4) = 17 ≡ 2 (mod 5)

그로 인해 해가 존재하는건  x ≡ 2 (mod 5), x ≡ 3 (mod 5)가 이차합동식의 해이다.

답을 작성할 때 해가 존재하는 경우 위와 같이 적어주고 해가 존재하지 않을 경우 해가 존재하지 않다. 라 작성하면 된다.

위 식에서 계산은 덧셈으로 하였을 때 항등원은 0이며, m = 5 이므로 5 = {0 ,1, 2, 3, 4}로 f(x)의 x값안에 차례대로 대입하여 계산한다.

반대로 

만약 식이 곱셉이였을 때 항등원은 1이며, m 또는 p로 0을 제외한 수로 대입하며 계산해야한다.

일차 합동식 ax ≡ b (mod m)이 해를 가지기 위해 필요충분조건 d = (a, m)과 d | b일 때 성립된다. 

d = (a, m) = gcd (a, m) 즉 최대공약수 1이 되야하며, d | b의 수가 약수, 배수 관계가 되면 가능하다.

위 식의 경우 곱셈으로 되어있는 일차합동식인데 (a x s) + (b x t) = 1이 성립이 되어야 하며, 식을 풀어 나갈 때 "확장된 유클리드 알고리즘"으로 계산 해야한다. 

r = r_1 - (q × r_2 ), S = S1 - (q × S2 ), t = t1 (q x t2 )

r = 나머지

Wilson의 정리란 임의의 소수 p에 대하여 (p - 1)! ≡ -1 (mod p)이고 p는 소수, m은 합성수이다.

예시로 작성한 식으로 p = 5에 대하여 (p - 1)! ≡ -1 (mod p)가 성립함을 보여라

소수

법 5에서 1과 합동인 p-3/2 = 1개가 나온다.

5의 소수는 5 = {2, 3}

2 x 3 ≡ 1(mod 5)

( 2 x 3 ) ≡ 1 (mod 5)

3! ≡ 1 (mod 5)

양변에 6을 곱하면 

6! ≡ 6 (mod 5)

이고

6 ≡ -1 (mod 5)

이기에

6! ≡ -1 (mod 5) 이다.

합성수

(8-1)! = 7!  = 5040 ≡ 0 (mod 8)

윌슨의 정리는 팩토리얼과 유사하다 생각하면 편하다.

▶팩토리얼은 1부터 지정된 수 만큼 곱하는 방식이다.

소수 p일 때는 값이 -1, 합성수 m 일 때 0이 나온다.

역원이란 두 원소를 연산한 결과가 항등원일 때, 한 편에 대하여 다른 편을 이르는 말이다. 덧셈에서의 반수와 곱셈에서의 역수를 일반화한 개념이다.

곱셈의 항등원은 a x b ≡ 1 (mod m), 덧셈의 항등원은 a + b ≡ 0 (mod m)이다.

모듈러 연산에서 각각의 정수는 덧셈, 곱셈에 대한 역원을 갖는다. a * b, a + b의 합동은 1과 0이다.

위 연산이 자기자신도 물론 가능하다. 단 m값보다 작게 나와야 한다. 

a = 8, b = 6, m = 49으로 계산하면 a x b = 48 ≡ 1 (mod 49) 

※ mod 모듈러는 나눗셈이라 생각하면 편하다.

임의의 정수 a ∈ Zm 가 곱셈에 대한 필요충분조건은 gcd(a, m) = 1이 되어야 한다. 

위 조건은 무조건 성립해야한다. 

m의 값이 소수일 경우 곱셈이 역원이 존재, m의 값이 합성수일 때 존재하거나 존재하지 않는다. 

역원을 구할 때는 "확장된 유클리드 알고리즘"을 이용한다.

(m x s) + (b x t) = gcd(m, b) 

이때도 gcd(m, b) =1, 최대공약수 1이 꼭 되어야 한다. 

즉 (m x s) + (b x t)  = 1 ↔  b x t ≡ 1 (mod m)과 같다.   

잉여계란 집합을 말하고 이는 크게 2개 완전잉여계와 기약잉여계가 존재한다.

나눗셈관계식에서 나온 r = 나머지 = 잉여를 뜻하고 잉여류는 정수를 m으로 나누었을 때 나머지가 같은 정수를 모아놓은 집합이며, (완전/기약) 잉여류는 잉여류를 모아놓은 집합이다.  

잉여계를 계산할 때 mod m, mod p를 중심으로 합동식을 계산해야 하며 이는 법 m에 관한 완전잉여계, 법 p에 관한 기약잉여계라 부르고 완전잉여계는 Z, 기약잉여계는 Z*로 표시한다. 

완전잉여계에서는 Z = {0, ...., m-1} 까지이고 기약잉여계는 Z* = { 1 , ...., m -1} 로 시작한다. 차이점은 0이 들어가냐 안들어가냐이다.

나머지의 집합을 모아놓았기에 현대대수학, 이산대수등의 식이 사용된다.

합동식이란 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다.

 modular라 말하며, 계산에서 "mod"로 쓰이는 모듈러 연산자이다.

mod는 × 나 ÷ 와 동일하게 쓰인다.

식으로 표현하면 17 mod 14 = 3으로 나타낼 수 있다.

(17을 14로 나누면 나머지가 3 이랑 동일하다)

https://beru-123.tistory.com/11 에서 나눗셈과 관계식에 대해 설명한 이유는 합동식에서 계속해서 사용하였기에 참고하면서 공부하면 많은 도움이 된다. 

mod m(합성수), p(소수)은(는)  z = { 1, 2, 3, 4, 5} 등과 같은 정수 집합을 가지고 합동식에 사용이 되며, -1과 같은 마이너스의 값일 경우 mod "m", "p"일 때 "역원"을 사용하여 계산한다. 

예시로 설명하자면 -49 mod  15 일 때, 15를 구구단식으로 사용한다. 15 x 2 = 30, 15 x 3 = 45 이를 말하는 거와 같다.

아무튼 다시 식을 계산하면 -49는 45로 계산할 때 모듈값 -4가 나오므로 식이 성립되지 않는다 하지만 15 x 4 = 60이다.

그렇다면 60 - 49 = 11이다. 

즉, ∴  -49 mod 15 ≡ 11 이 답을 말한다. 

-4 = 11과 동일하다는 게 합동식 역원에 의미를 뜻한다.

11은 역원, 모듈러는 15, 나눠야 할 수는 -49 인 것이다.  

합동식의 동치관계

a ≡ a (mod m) : 반사 관계

a ≡ b (mod m) 이면 b ≡ a (mod m)이다. : 대칭관계

a ≡ b (mod m)이고 b ≡ c (mod m)이면  c ≡ a (mod m)이다 : 추이관계

임의의 정수인 법(집합) m에 관하여 m = 숫자만큼 반드시 합동이다. 

두 정수 a와 b에 대하여 다음 성질을 동치이다.

1. a - b가 m의 배수이며, a - b = mk, (k ∈ Z)이다.
2. a와 b는 m을 법으로 합동이다. a ≡ b (mod m)이다.
3. gcd(a, m) = gcd(b, m)이다. 

※ gcd는 최대공약수를 뜻하며, 동치관계는 알아두면 좋다.  

이해가 안 돼 신다 하면 댓글로 최대한 설명하겠습니다.