# 합성수 m이 m과 서로소인 모든 a에 대해 합동식 a^(m-1) = 1 (mod m)을 만족하면 카마이클 수라고 한다.
# a) m = 561 = 3*11*17이 카마이클 수임을 증명하여라. (도움말, 가능한 모든 320개의 a에 대하여
# a^(m-1) = 1 (mod m))을 계산할 필요는 없다. 실제로, 페르마의 소정리를 이용하여 m을 나누는 각각의 소수 p에 대하여
# a^(m-1) = 1 (mod p)임을 학인하고, 이것이 왜 a^(m-1) = 1 (mod m)을 유도하는지 설명하라.
# 다른 카마이클 수를 찾아보라. 카마이클 수가 무한히 많을까?
from number_util import *
# 카마이클 수인지 정의대로 판정하는 함수
# 일일이 검사하므로 시간이 많이 걸림
def isCarmichael(m):
if isPrime(m) == True: # 소수는 카마이클 수가 아님.
return False
for a in range(m):
if a ** m % m != a:
return False #print("a는 합성수이지만 카마이클 수는 아닙니다.")
return True
# 소인수분해하여 소인수들에 대해서만 mod n을 검사한다. 따라서 속도가 빠르다.
def isCarmichael2(n):
if isPrime(n) == True: # 소수는 카마이클 수가 아님.
return False
res = factorize2(n) # 소인수분해 결과를 딕셔너리로 받는다
lst = []
for key, value in res.items(): # {7: 1, 19: 1, 67: 1}
if value != 1:
return False # 소인수의 지수가 1이 아니라면 카마이클 수가 아님.
lst.append(key)
for a in lst: # [7, 19, 67]
if a ** n % n != a: # 7 ^ n % n = 7 임을 확인.
return False
return True # 조건을 만족시켰으므로 카마이클 수임
# 카마이클 수 관련해서 m이 합성수라는 증인 목록을 만든다.
# 증인 갯수, 증인 비율, (증인 목록)을 반환한다.
def compositeWitness(m):
witnesses = []
if isPrime(m) == True: # 소수는 카마이클 수가 아님.
return witnesses
for a in range(2, m):
if a ** m % m != a:
witnesses.append(a)
return len(witnesses), len(witnesses)/m, witnesses
# 3에서 20까지 각 숫자에 대해 합성수 증인들과 그 비율을 찾음
# '친절한 수론 길라잡이' 19장 134쪽 표 내용
for i in range(3, 21):
print(i, compositeWitness(i))
print()
# 19장 133쪽 내용
numbers = [287, 190, 314, 586, 935, 808, 728, 291]
for n in numbers:
print(n, compositeWitness(n)[0:2]) # 증인 목록이 너무 길어서 목록 출력은 제외
print()
# 카마이클 수인지 확인
num = [561, 1105, 1729, 2465, 2821, 6601, 8911, 62745, 423899]
# n 이하의 모든 수를 다 검사하지 않고, n을 인수분해해서 그 소인수들에 대해서만 검사
for n in num:
print(n, isCarmichael2(n))실행:
3 []
4 (2, 0.5, [2, 3])
5 []
6 (2, 0.3333333333333333, [2, 5])
7 []
8 (6, 0.75, [2, 3, 4, 5, 6, 7])
9 (6, 0.6666666666666666, [2, 3, 4, 5, 6, 7])
10 (6, 0.6, [2, 3, 4, 7, 8, 9])
11 []
12 (8, 0.6666666666666666, [2, 3, 5, 6, 7, 8, 10, 11])
13 []
14 (10, 0.7142857142857143, [2, 3, 4, 5, 6, 9, 10, 11, 12,
13])
15 (6, 0.4, [2, 3, 7, 8, 12, 13])
16 (14, 0.875, [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
17 []
18 (14, 0.7777777777777778, [2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14, 15, 16, 17])
19 []
20 (16, 0.8, [2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
17, 18, 19])
287 (278, 0.9686411149825784)
190 (150, 0.7894736842105263)
314 (310, 0.9872611464968153)
586 (582, 0.9931740614334471)
935 (908, 0.9711229946524064)
808 (804, 0.995049504950495)
728 (720, 0.989010989010989)
291 (282, 0.9690721649484536)
561 True
1105 True
1729 True
2465 True
2821 True
6601 True
8911 True
62745 True
423899 False