# 합동 다항식의 해를 함수를 사용해서 편리하게 구하는 방법과
# 함수를 사용하지 않고 for문으로 단순하게 구하는 방법을 구현한다.
# 함수를 사용하는 방법은, 다항식의 차수와 계수를 딕셔너리 자료형으로 함수에 넘겨주고 m 값도 함께 넘져주면,
# 그 값을 가지고 fx가 mod m 으로 0이 되는 x값들을 구해 리스트로 반환한다.
# 먼저 다항식 수식을 직접 입력해서 for문으로 돌리는 불편한 방식부터...
# '친절한 수론 길라잡이' 합동 65쪽 연습문제8.8
# "자연수 m과 정수 계수 다항식 f(X)를 입력하면, 합동방정식
# f(X) = 0(mod m)
# 의 모든 해를 구하는 프로그램을 만들어라. (어렵게 생각하지 말고 X = 0, 1, 2, ..., m-1을 대입하여
# 어떤 것이 해가 되는지 확인하는 프로그램이면 족하다. 이 프로그램을 다음 다항식
# f(X) =X^11 + 21X^7 + 8
# 과 다음 m에 대하여 실험해 보아라
# m = {130, 137, 144, 151, 158, 165, 172}"
m = [130, 137, 144, 151, 158, 165, 172]
#fx = x ** 11 + 21*(x**7) + 8
for i in range(len(m)):
lst = []
for j in range(0, m[i]):
fx = j**11 + 21*(j**7) + 8
if fx % m[i]== 0:
lst.append(j)
print("m = {}: ".format(m[i]), end="")
print(len(lst), "개", lst)
print("---------------------")
# 연습문제 8.9
# 다음 합동방정식은 몇 개의 서로 다른 해를 갖는가?
# X^4 + 5X^3 + 4X^2 -6X -4 = 0 (mod 11) 0 <= X <11
m = [11]
for i in range(len(m)):
lst = []
for j in range(0, m[i]):
fx = j**4 + 5*(j**3) + 4*(j**2) - 6*j - 4
if fx % m[i]== 0:
lst.append(j)
print("m = {}: ".format(m[i]), end="")
print(len(lst), "개", lst)
# 연습문제 8.9.b
m = [8]
for i in range(len(m)):
lst = []
for j in range(0, m[i]):
fx = j**2 - 1
if fx % m[i]== 0:
lst.append(j)
print("m = {}: ".format(m[i]), end="")
print(len(lst), "개", lst)
# 연습문제 8.10
# p, q가 소로 다른 소수라 가정하자. 다음 합동방정식은 서로 다른 해를 최대 몇 개 가질 수 있나?
# m 이 소수p와 소수q의 곱일 때
m = [21, 6, 15, 33, 77, 55]
for i in range(len(m)):
lst = []
for j in range(0, m[i]):
fx = j**2 - 1
if fx % m[i]== 0:
lst.append(j)
print("m = {}: ".format(m[i]), end="")
print(len(lst), "개", lst) # 최대 4개
# 다항식 합동식의 해를 함수를 이용해 구한다.
# f(x) 가 x^4 + 5*x^3 + 4*x^2 - 6*x^1 - 4*x^0 이라면 차수와 계수를 딕셔너리 형태로 넘겨준다.
# m도 같이 넘겨주면, 아래 함수에서는 f(x)가 mod m 으로 0일 때를 계산해서 그 x값 리스트를 돌려준다.
# {4:1, 3:5, 2:4, 1:-6, 0:-4}
# 1* (x ** 4) + 5*(x**3) + 4*(x**2) + -6*(x**1) + -4*(x**0)
def congruence_equation_poly(poly, m):
# poly = {차수:계수, 차수:계수, 차수:계수....}
lst = []
for i in range(0, m): # 0 <= i < m 에서 ...
fx = 0 #함수값은 0으로 초기화하고 높은 차수부터 차례로 누적한다.
for d, c in poly.items(): # 딕셔너리 크기만큼 반복 d: 차수, c: 계수
fx += c * (i ** d) # fx 함수값을 계속 누적해서 구한다.
if fx % m == 0: # 함수값이 구해졌으면 mod m으로 합동인지 검사한다.
lst.append(i) # 합동이면 정답이므로, 목록에 추가한다.
return lst
print("\n============================")
ms = [130, 137, 144, 151, 158, 165, 172]
for m in ms:
#fx = x ** 11 + 21*(x**7) + 8
poly = {11:1, 7:21, 0:8}
res = congruence_equation_poly(poly, m)
print("m = {}: {}".format(m, res))
print("----------------------")
# X^4 + 5X^3 + 4X^2 -6X -4 = 0 (mod 11) 0 <= X <11
poly = {4:1, 3:5, 2:4, 1:-6, 0:-4}
m = 11
res = congruence_equation_poly(poly, m)
print("m = {}: {}".format(m, res))
# fx = x**2 - 1 (mod 8)
poly = {2:1, 0:-1}
m = 8
res = congruence_equation_poly(poly, m)
print("m = {}: {}".format(m, res))
# fx = x^2 - 1
poly = {2:1, 0:-1}
ms = [21, 6, 15, 33, 77, 55]
for m in ms:
res = congruence_equation_poly(poly, m)
print("m = {}: {}".format(m, res))결과:
m = 130: 0 개 []
m = 137: 1 개 [100]
m = 144: 0 개 []
m = 151: 1 개 [50]
m = 158: 4 개 [25, 32, 104, 111]
m = 165: 0 개 []
m = 172: 2 개 [14, 100]
---------------------
m = 11: 2 개 [1, 9]
m = 8: 4 개 [1, 3, 5, 7]
m = 21: 4 개 [1, 8, 13, 20]
m = 6: 2 개 [1, 5]
m = 15: 4 개 [1, 4, 11, 14]
m = 33: 4 개 [1, 10, 23, 32]
m = 77: 4 개 [1, 34, 43, 76]
m = 55: 4 개 [1, 21, 34, 54]
============================
m = 130: []
m = 137: [100]
m = 144: []
m = 151: [50]
m = 158: [25, 32, 104, 111]
m = 165: []
m = 172: [14, 100]
----------------------
m = 11: [1, 9]
m = 8: [1, 3, 5, 7]
m = 21: [1, 8, 13, 20]
m = 6: [1, 5]
m = 15: [1, 4, 11, 14]
m = 33: [1, 10, 23, 32]
m = 77: [1, 34, 43, 76]
m = 55: [1, 21, 34, 54]