유한체 곱셈과 나눗셈

곱셈

유한체에서 닫혀 있는 덧셈 $+_f$ 을 정의했듯이 유한체에서 닫혀 있는 곱셈도 정의할 수 있다.
이를 이용하여 같은 숫자를 여러 번 곱하는 거듭제곱도 정의할 수 있다.

예를들어, 위수 19의 유한체 $F_{19}$ 에서 보면,
$5 *_f 3$ = (5 * 3)%19 = 15
$8 *_f 17$ = (8 * 17)%19 = 3 

곱셈 결과가 직관적이지 않다. 그러나 그 때문에 곱셈에 대해서 닫혀 있게 된다. 곱셈의 결과는 항상 집합 {0, 1, ...., p-1} 에 속하게 된다.
다시 말해 유한체 안에서 정의된 연산 결과는 항상 그 유한체 안에 속해야 한다.

그리고 유한체에서도 나머지 연산을 이용하여 거듭제곱 을 할 수 있다.
$F_{19}$ 에서, 

$7^3$ = (7 * 7 * 7)%19 = 1
$9^{12}$ = 7

 

연습문제 1.5
k 가 각각 1, 3, 7, 13, 18 인 경우 $F_{19}$ 에서 다음 집합을 구하고, 구한 집합에서 어떤 규칙성이 있는지 찾아라.
{ $k *_f 0, k *_f 1, k *_f 2, k *_f 3, ... , k *_f 18$}

 

# 내가 만든 코드
prime = 19
kSet = [1, 3, 7, 13, 18]
tempList = []
for k in kSet:
  for i in range(0, prime):
    tempList.append((k * i) % prime)
  print(sorted(tempList))
tempList = []

# 정답 코드
prime = 19
for k in (1, 3, 7, 13, 18):
print(sorted([k * i % prime for i in range(prime)]))



출력결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]

연습문제 1.7
7, 11, 17, 31 인 p 값에 대해 유한체 $F_p$ 에서 다음 집합을 구해라 
{ $1^{(p-1)}, 2^{(p-1)}, 3^{(p-1)}, 4^{(p-1)} ... , (p-1)^{(p-1)}$ }

 

primes = [7, 11, 17, 31]

for p in primes:
	print([(i ** (p - 1)) % p for i in range(1, p)])
	print([pow(i, (p - 1), p) for i in range(1, p)])  # pow 사용

출력결과
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

 

소수인 p 와 0 보다 큰 n(여기서 n은 p-1까지임) 에 대해 $n^{(p-1)}$ 은 항상 1 이다.
즉, $n^{(p-1)}$ %p = 1 이다(페르마의 소정리로 증명 가능)

 

페르마의 소정리 증명

위에 있는 연습문제 1.5 결과를 이용한다. k가 소수면, 집합의 결과는 항상  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18] 이다. 즉 아래와 같은 공식이 성립한다. 

 

 

{ $k *_f 0, k *_f 1, k *_f 2, k *_f 3, ... , k *_f (p-1)$} = $F_p$

 

k를 n 으로 바꾸면 { $n *_f 0, n *_f 1, n *_f 2, n *_f 3, ... , n *_f (p-1)$} 이고 {0n%p, 1n%p, 2n%p, 3n%p, (p-2)n%p, (p-1)n%p} 이다.

결국 $F_p$ = {0, 1, 2, 3, ..., p-2, p-1} = {0, n%p, 2n%p, 3n%p, (p-2)n%p, (p-1)n%p} 공식이 성립한다.

좌항 우항 모두 같은 집합이기 때문에 왼쪽 원소끼리 곱셈한 결과와 오른쪽 원소끼리 곱한 결과는 동일하다.

 

책(p53)에 있는대로 곱한 결과를 정리해보면,
(p-1)! %p = (p-1)! $n^{(p-1)}$ %p 다. 양쪽을 (p-1)! 로 약분하면 
1!%p = $n^{(p-1)}$ %p 가 되고
1 = $n^{(p-1)}$ %p 가 된다.

 

나눗셈

유한체 나눗셈은 일반 대수와 마찬가지로 0으로 어떤 값을 나눌 수는 없다.

$F_{19}$ 에서,
$3*_f 7$ = 21%19 = 2 로부터 $2/_f 7 = 3$ 등식이 성립한다.
$9*_f 5$ = 45%19 = 7 로부터 $7/_f 5 = 9$ 등식이 성립한다.

 

유한체 원소끼리의 나눗셈이기 때문에 일반 수학 상식에서의 나눗셈과 다르다. 상식과 다르기 때문에 유한체에서 닫혀 있는 나눗셈이 가능해진다.

$3*_f 7 = 2$ 를 모르는 상황에서 $2/_f 7$ 를 어떻게 계산할 수 있을까?
나눗셈은 곱셈의 역연산이기 때문에 다음과 같이 쓸 수 있다.
a/b = $a *_f (1/b)$ = $a *_f b^{-1}$

 

여기서 $b^{-1}$ 을 안다면 나눗셈 문제가 곱셈문제로 바뀐다. 그리고 $b^{-1}$ 를 계산하는데 페르마의 소정리가 활용된다. 페르마의 소정리에 따르면 $n^{(p-1)}$ %p = 1 이다.

 

$b^{(p-1)}$ = 1 이고 p는 소수기이게
$b^{-1}$ = $b^{-1}$ $*_f$ 1
= $b^{-1}$ $*_f$ $b^{(p-1)}$ = $b^{(p-2)}$ 이다. 이를 요약하면 다음과 같다.
$b^{-1}$ = $b^{(p-2)}$

 

$F_{19}$ 에서,
$2/_f 7$ = $2*_f 7^{-1}$ = $2*_f 7^{17}$ = 3
$7/_f 5$ = $7*_f 5^{-1}$ = $7*_f 5^{17}$ = 9

 

연습문제 1.8
$F_{31}$ 에서,
1. $3 /_f 24$ = $3 *_f 24^{-1}$ = $3 *_f 24^{29}$ = 4 
3. $17^{-3}$ 
 $b^{-3} = b^{(p-4)}$ 니까 $17^{(31-4)}$ % 31 = 29 
3. $4^{-4} *_f 11$ = $11 * 4^{(31-5)}$ % 31 = 13 

 

연습문제 1.9
두 유한체 원소 간의 나눗셈을 정의하는 __truediv__ 메서드 작성해라.

# 내가 작성한 코드
def __truediv__(self, other):
	if self.prime != other.prime:
		raise TypeError('Cannot div two numbers in different Fields')
	num = self.num * pow(other.num, self.prime - 2) % self.prime
	return self.__class__(num, self.prime)

# 책에 있는 답
def __truediv__(self, other):
	if self.prime != other.prime:
		raise TypeError('Cannot div two numbers in different Fields')
	num = self.num * pow(other.num, self.prime - 2, self.prime) % self.prime
	return self.__class__(num, self.prime)

 

 

 

출처: 밑바닥부터 시작하는 비트코인