AKS 소수성 테스트 Rosetta 코드는 어떻게 그렇게 간단합니까?
대체 질문을 보려면 끝으로 건너 뛰십시오.
다음은 AKS Primality Test 의 Python 구현입니다 .
from sympy import *
def expand_x_1(n):
# This version uses a generator and thus less computations
c = 1
for i in range(n//2 + 1): # // means flooring after divide
c = c*(n - i)//(i + 1)
yield c
def aks(p):
if p==2:
return True
for i in expand_x_1(p):
if i % p:
# we stop without computing all possible solutions
return False
return True
for n in range(2, 10000):
primality = aks(n)
primality1 = isprime(n)
if primality != primality1:
print("Fails @", n) # Never prints
assert (0)
else:
print(primality)
알고리즘의 훨씬 더 심층적 인 의사 코드 (다항식 연산 포함)를 가져 와서이 10 줄 버전으로 변환하는 것이 어떻게 가능할까요?
위의 것이 실제로 AKS 소수성 테스트입니까? 나는 그것을 얻었다 :
https://rosettacode.org/wiki/AKS_test_for_primes#Python
입력을 호출하자 $n$, 아닙니다 $p$.
의 코드 expand_x_1(n)는 다음을 계산해야합니다.
$$c_0 = 1, c_i = \lfloor \dfrac{c_{i-1}(n-i)}{i + 1}\rfloor$$
어디 $c_i = $ 그만큼 $i$th는 가치를 산출했습니다. 이 값을 사용하는 다른 코드는 단순히$c_i \neq 0 \pmod n$,이 경우 (true 인 경우) False복합에 대해 반환 됩니다. Else if for all$c_i$ 값 $i = 0..\lfloor \dfrac{n}{2} \rfloor + 1$ 우리는 $c_i = 0 \pmod n$, 그런 다음 True반환됩니다.
재귀와이 테스트는 AKS 알고리즘을 구성하는 것과 전혀 다른 것 같습니다. 그래서 저는 분석적인 숫자 이론가가 공식을 설명 할 수 있기를 바랐습니다.
또는 위의 질문에 답할 수없는 경우 :
공식을 어떻게 연구 할 수 있습니까? $c_i$; 당신은 그것이 가진 어떤 재 배열을 생각할 수 있습니까? 예를 들어 분모가 바닥 등이있는 재귀 하위 호출에서 결합 될 수 있습니다.
이것은이 공식에 대해 다른 질문을 열 필요가 없기 때문입니다.
예를 들어 코드를 다음과 같이 수정했습니다.
def expand_x_1(n):
c = 1
d = 1
for i in range(n//2 + 1):
d *= (i + 1)
c = c*(n - i)
yield c//d
나는 그것을 실행할 때 더 실패를 받고 없습니다 이후 그러므로, 나는 다소 안전 "분모가 결합 될 수있다"고 추측 할 수 수학적으로, 즉에서 해당 도출 사용했다 일부의 신원이 바닥의 기본 속성은 .
또 무엇을 말할 수 있으며이 공식은 다항식 산술과 어떤 관련이 있습니까?
답변
라벨을 지정한 번호 $c_i$이다 이항 계수 $\binom ni$; 코드는$\binom ni \equiv 0 \pmod n$ 모든 $0 < i \le \frac n2$. 이것은 AKS 알고리즘 이 아닙니다 . AKS 알고리즘 에 동기 를 부여 하기 위해 Wikipedia 기사 에 나열된 지수 시간 무차별 대입 알고리즘입니다.