Python을 사용하여 소수를 감지하는 방법의 예

이 글은 Python 소수 검출 방법을 주로 소개하고 있으며, Python 소수 검출 관련 기술을 예시로 분석하고 있습니다. 자세한 내용은 다음과 같습니다.

요인 검출:

검출 요소, 시간 복잡도 O(n^(1/2))

def is_prime(n):
  if n < 2:
    return False
  for i in xrange(2, int(n**0.5+1)):
    if n%i == 0:
      return False
  return True

페르마의 작은 정리:

n이 소수이고 a가 n보다 작은 양의 정수이면 a의 n제곱은 는 모듈로 n

과 일치합니다.

구현 방법:

진수(예: 2)를 선택합니다. 큰 정수 p의 경우 2^(p-1)과 1이 모듈로 p가 일치하지 않으면 p는 다음이 아니어야 합니다. 그렇지 않으면 p는 소수일 가능성이 높습니다.
2**(n-1)%n은 계산하기 쉬운 숫자가 아닙니다.

모듈식 연산 규칙:

(a^b) % p = ((a % p)^b) % p
(a * b) % p = (a % p * b % p) % p

X^N(% P) 계산

예
N이 짝수이면 X^N = (X *X)^[N/2];
N이 홀수이면 X^N = X*X^(N-1) = X *(X*X)^[N/2];

def xn_mod_p(x, n, p):
  if n == 0:
    return 1
  res = xn_mod_p((x*x)%p, n>>1, p)
  if n&1 != 0:
    res = (res*x)%p
  return res

또한 다음 알고리즘으로 요약하면 두 함수는 동일합니다

def xn_mod_p2(x, n, p):
  res = 1
  n_bin = bin(n)[2:]
  for i in range(0, len(n_bin)):
    res = res**2 % p
    if n_bin[i] == '1':
      res = res * x % p
  return res

빠른 모듈러 지수화 처리로 페르마 테스트를 구현할 수 있습니다

Fermat 검정은 부정적인 결론이 나올 때는 정확하지만 긍정적인 결론이 틀릴 수도 있고, 큰 정수에 대해서는 매우 효율적이며, 정수가 커질수록 오판단 비율이 감소합니다

def fermat_test_prime(n):
  if n == 1:
    return False
  if n == 2:
    return True
  res = xn_mod_p(2, n-1, n)
  return res == 1

MILLER-RABIN 검출

Miller -라빈 검출은 현재 널리 사용되는 2차 검출입니다

정리: p가 소수이고 0페르마의 작은 정리: a^(p-1) ל 1(mod p)

밀러-라빈 소수 검정의 방법입니다. 인덱스 n-1에서 인수 2를 연속적으로 추출하고, n-1을 d*2^r(여기서 d는 홀수)로 표현합니다. 그런 다음 우리가 계산해야 할 것은 a를 n으로 나눈 d*2^r 거듭제곱의 나머지가 됩니다. 따라서 a^(d * 2^(r-1))은 1과 같거나 n-1과 같습니다. a^(d * 2^(r-1))이 1과 같으면 정리는 a^(d * 2^(r-2))에 계속 적용되고 제곱근은 다음과 같은 방식으로 계속됩니다. ^는 특정 i (d * 2^i) mod n = n-1에 대해 만족되거나 마지막 지수의 2가 a^d mod n=1 또는 n-1을 얻는 데 사용됩니다. 이런 식으로 페르마의 작은 정리는 다음과 같은 형태로 강화됩니다:

인수 2를 최대한 추출하고 n-1을 d*2^r로 표현합니다. n이 소수이면 a^d mod n입니다. =1, 또는 i가 a^(d*2^i) mod n=n-1 (0<=i

정리: n이 소수이고 a가 n보다 작은 양의 정수이면 n에 대한 a를 기반으로 한 밀러 테스트가 참입니다.
밀러 테스트는 k번 수행됩니다. , 합성수를 소수로 취급하는 오류 확률은 최대값이 4^(-k)

def miller_rabin_witness(a, p):
  if p == 1:
    return False
  if p == 2:
    return True
  #p-1 = u*2^t 求解 u, t
  n = p - 1
  t = int(math.floor(math.log(n, 2)))
  u = 1
  while t > 0:
    u = n / 2**t
    if n % 2**t == 0 and u % 2 == 1:
      break
    t = t - 1
  b1 = b2 = xn_mod_p2(a, u, p)
  for i in range(1, t + 1):
    b2 = b1**2 % p
    if b2 == 1 and b1 != 1 and b1 != (p - 1):
      return False
    b1 = b2
  if b1 != 1:
    return False
  return True
def prime_test_miller_rabin(p, k):
  while k > 0:
    a = randint(1, p - 1)
    if not miller_rabin_witness(a, p):
      return False
    k = k - 1
  return True

를 초과하지 않습니다.

위 내용은 Python을 사용하여 소수를 감지하는 방법의 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!