(정수론/파이썬) 큰 숫자 소수 판정하기 (페르마 정리 이용)

# 연습문제 16.4
# "다음과 같이 주어진 수 n이 합성수인지 아니면 소수일 수도 있는지를 판정하는 프로그램을
# 만들어 보자. 2와 n - 1사이에서 10개의 수 a1, a2, ..., a10 을 고르고, 각각의 ai에 대하여
# ai(n-1) mod n을 계산한다. 만일 어떤 ai에 대하여 ai(n-1) != 1 (mod n)이라면 
# 'n은 합성수'를 출력하라. 만일 모든 ai에 대하여 ai(n-1) = 1 (mod n)이라면 'n은 아마도 소수'
# 를 출력하라."

import random 
from number_util import *

# 큰수가 소수인지 아닌지 판정한다. 페르마 소정리를 이용. 
# '아마도 소수'에는 아주 가끔 합성수가 끼어 있는 경우가 있다.
def isPrimeGuess(n):
  MAX_NUM = 1000   # 난수를 이 수치만큼 발생

  # 2와 N - 1 사이에서 10개의 수를 고른다. 
  # n과 서로소인 수를 고르는 게 좋겠지만 그 자체에 자원이 꽤 소모되므로 단순한 방식으로.
  a_s = []
  for i in range(MAX_NUM):
    a = random.randrange(2, n)
    if gcd(a, n) != 1: continue
    a_s.append(a)   # 2 ~ n - 1
  #print(a_s)   # 생성된 10개의 난수

  maybe_prime = True
  for i in range(MAX_NUM):
    if successiveSquaring2(a_s[i], n-1, n) != 1:  # ai(n-1) mod n 계산
      maybe_prime = False   # composite number
      break
  if maybe_prime: 
    print(f"{n} 은 아마도 소수")
  else:
    print(f"{n} 은 합성수")


ns = [7387, 7393, 9991, 283976710803263, 
    243034209889348945908458903908324908449804908434389747894389438943,
    36799544363760852850158472813746772001249695467027553135084459191495404143126861597208894503131059724016325719,
    3076382403662644884917201315295252005693733018156832251827714417,
    9384466541846136291283431686887587738373709251831730903]

for n in ns:
  isPrimeGuess(n)

# print("-----------")
# for n in ns:
#   if isPrime(n):
#     print(f"{n} 은 소수")
#   else:
#     print(f"{n} 은 합성수")

결과:

7387 은 합성수
7393 은 아마도 소수
9991 은 합성수
283976710803263 은 합성수
243034209889348945908458903908324908449804908434389747894389438943 은 합성수
36799544363760852850158472813746772001249695467027553135084459191495404143126861597208894503131059724016325719 은 합성수
3076382403662644884917201315295252005693733018156832251827714417 은 합성수
9384466541846136291283431686887587738373709251831730903 은 아마도 소수

 

(참고: 확인했을 때 다른 수는 다 옳게 판정했다. 367995...는 합성수라고 판정했고 페르마 정리에 의해 참이라고 볼 수 있다. 확인해보기 위해 UINT_MAX (C 언어의 unsigned int 의 최대값) 이하의 소수들(제일 큰 값은 4,294,967,291)로 나누어봐도 나누어 떨어지는 값이 없었다. 어쨌든 합성수이긴 하나 소인수분해를 하기가 아주 곤란한 숫자다.)