카테고리 없음
(정수론/파이썬) 합동식을 이용해 소수 판별하기
미친토끼
2021. 9. 8. 15:09
# 소수 판정을 합동을 이용해 하기
# '친절한 수론 길라잡이' 연습문제 9.2 ~ 9.3
# 9.2 적당히 작은 소수 p에 대해 (p-1)! (mod p) 값을 관찰하면, (p-1)! (mod p) = p -1 이다.
# 이를 증명하라. p-1과 p는 서로소이므로, p-1로 양변을 나눌 수 있다.
# 그러면 (p-2)! = 1 (mod p)를 얻을 수 있다.
# 원식에서 (p-2)!를 1로 대체하면
# 원식을 이렇게 쓸 수 있는데 (p-1)(p-2)! = p-1 (mod p)
# (p-2)! = 1 (mod p)로 대체하면 (p-1)* 1 = p-1 (mod p)가 되어 참이 된다.
import math # math.factorial
# 제곱근까지 약수를 구해서 소수를 판정하는 알고리즘
def isPrime(num):
root_val = round(num ** 0.5) # 제곱근 값을 구한다
for i in range(2, root_val+1): # 제곱근값+1 까지만 약수를 조사해도 충분하다
if num % i == 0: # 중간에 나눠지면 소수가 아니다
return False
return True
# 적당히 작은 소수에 대해 (p-1)! (mod p) 계산
for i in range(2, 100):
if isPrime(i): # 작은 수 중 소수 찾기
value = math.factorial(i-1) % i # (i-1)! (mod i) 계산
print(i, ":", value) # i가 소수라면 mod 계산값은 i - 1 이 됨 # 수학적 증명 가능
print("----------------")
# 9.3 적당히 작은 합성수 m에 대해 (m-1)! (mod m)을 계산하여라. 소수의 경우와 같은 규칙성을 찾을 수 있는가.
# (4-1)! (mod 4) = 2
# (6-1)! (mod 6) = 0
# (8-1)! (mod 8) = 0
# 4를 제외하고는 (합성수 - 1)! (mod 그합성수) = 0 이 됨.
# 컴퓨터로 40,000까지의 합성수를 계산해도 0이 됐지만, 수학적 증명은 못하겠음.(개인적인 역량?)
# 적당히 작은 합성수에 대해 (m-1)! (mod m) 계산
for i in range(2, 50): # 작은 수 중 합성수 찾기
if isPrime(i) == False: # 합성수라면
value = math.factorial(i-1) % i # (i-1)! (mod i) 계산
print(i, ":", value) # i가 합성수면 mod 계산값은 0이 되는 경향
print("----------------")
# 위 합성수 검증을 수학적으로 하지 못하는 개인적 역량 관계로, 컴퓨터로 계산해서 어디까지 가능한지 확인하는 루틴.
# 40,000까지는 확인해봄
# 적당히 작은 합성수에 대해 (m-1)! (mod m) 계산
for i in range(2, 1000000000): # 작은 수 중 합성수 찾기
if isPrime(i) == False: # 합성수라면
value = math.factorial(i-1) % i # (i-1)! (mod i) 계산. 합성수는 대체로 0임
if value != 0:
print("********* i", ":", value) # i가 합성수면 mod 계산값은 0이 되는 경향
if i % 2000 == 0:
print(f"현재 {i}까지 확인 중")
###################################
# 합성수 소수 판별 루틴 비교
###################################
# isPrime(num): num의 제곱근까지 약수가 있는지 검사해서 없으면 소수로 판정.
# isPrime2(num): (num - 1)! (mod num)을 계산해서 결과가 num - 1이면 소수, 아니면 합성수(합성수는 나머지가 0으로 되는 경향)
# 제곱근까지 약수를 찾는 방식이, 팩토리얼을 구해 나누는 방식보다 훨씬 빠른 것을 알 수 있음.
# 10000까지 소수 찾는 시간: isPrime(): 0.1319초, isPrime2(): 14.54초
def isPrime2(num):
value = math.factorial(num-1) % num # 소수면 value = num - 1
if value == num - 1:
return True
else:
return False
import time
start = time.time()
for i in range(2, 10000):
if isPrime2(i):
print(i)
print("taken time: ", time.time()-start)
start = time.time()
for i in range(2, 10000):
if isPrime(i):
print(i)
print("taken time: ", time.time()-start)
결과:
2 : 1
3 : 2
5 : 4
7 : 6
11 : 10
13 : 12
17 : 16
19 : 18
23 : 22
29 : 28
31 : 30
37 : 36
41 : 40
43 : 42
47 : 46
53 : 52
59 : 58
61 : 60
67 : 66
71 : 70
73 : 72
79 : 78
83 : 82
89 : 88
97 : 96
----------------
4 : 2
6 : 0
8 : 0
9 : 0
10 : 0
12 : 0
14 : 0
15 : 0
16 : 0
18 : 0
20 : 0
21 : 0
22 : 0
24 : 0
25 : 0
26 : 0
27 : 0
28 : 0
30 : 0
32 : 0
33 : 0
34 : 0
35 : 0
36 : 0
38 : 0
39 : 0
40 : 0
42 : 0
44 : 0
45 : 0
46 : 0
48 : 0
49 : 0
----------------
********* i : 2
현재 2000까지 확인 중
현재 4000까지 확인 중
현재 6000까지 확인 중
현재 8000까지 확인 중
현재 10000까지 확인 중
..............