1.7 유한체 나눗셈

유한체 나눗셈은 일반 대수와 마찬가지로 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)}$ cf) %p 연산들은 다 어떻게 된걸까?

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

연습문제 1.8

$F_{31}$ 에서,

$3 /_f 24$ = $3 _f 24^{-1}$ = $3 _f 24^{29}$ = 4 print(3 * (24 ** 29) % 31)
$17^{-3}$ $b^{-3} = b^{(p-4)}$ 니까 $17^{(31-4)}$ % 31 = 29 print((17 ** 27) % 31)
$4^{-4} _f 11$ = $11 4^{(31-5)}$ % 31 = 13 print(11 * (4 ** 26) % 31)

연습문제 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)

yangbongsoo / blockStudy

1.7 유한체 나눗셈 #5

연습문제 1.8

연습문제 1.9