Python의 Aks Primes 알고리즘

StackOverflow https://stackoverflow.com/questions/347811

  •  20-08-2019
  •  | 
  •  

문제

몇 년 전, 그것은 입증되었습니다 프라임은 p에 있습니다. 알고리즘 구현이 있습니까? 그들의 원시 테스트 파이썬에서? 순진한 발전기로 벤치 마크를 실행하고 얼마나 빨리 있는지 직접보고 싶었습니다. 나는 그것을 직접 구현할 것이지만, 나는 아직 그렇게하기에 충분한 종이를 이해하지 못한다.

도움이 되었습니까?

해결책

빠른 답변 : 아니요, AKS 테스트는 Primality를 테스트하는 가장 빠른 방법이 아닙니다. 많은 것이 있습니다 많이 (일반화 된) Riemann 가설을 가정하거나 무작위 화 된 더 빠른 원시 테스트. (예 : 밀러-라빈 빠르고 구현하기가 간단합니다.)이 논문의 실제 획기적인 것은 이론적이며 결정 론적 다항식 시간 알고리즘은 GRH 또는 기타 예측되지 않은 추측을 가정하지 않고 원시성을 테스트하기 위해 존재합니다.

즉, 이해하고 구현하고 싶다면 Scott Aaronson의 짧은 기사 도움이 될 수 있습니다. 모든 세부 사항으로 들어가는 것은 아니지만 12/12 페이지에서 시작할 수 있으며 충분히 제공합니다. :-) 또 한있다 구현 목록 (대부분 C ++).

또한 최적화 및 개선을 위해 (여러 순서로)를보고 싶을 수도 있습니다. 이 보고서, 또는 (나이) 크 랜달과 파파도풀로스의 보고서, 또는 (나이가 많은) Daniel J Bernstein의 보고서. 그들 모두는 상당히 상세한 의사 코드를 가지고있어 구현에 적합합니다.

다른 팁

예, 보러 가십시오 프라임에 대한 AKS 테스트 Rosettacode.org의 페이지

def expand_x_1(p):
    ex = [1]
    for i in range(p):
        ex.append(ex[-1] * -(p-i) / (i+1))
    return ex[::-1]

def aks_test(p):
    if p < 2: return False
    ex = expand_x_1(p)
    ex[0] += 1
    return not any(mult % p for mult in ex[0:-1])
    print('# p: (x-1)^p for small p')
    for p in range(12):
        print('%3i: %s' % (p, ' '.join('%+i%s' % (e, ('x^%i' % n) if n else '')
                                   for n,e in enumerate(expand_x_1(p)))))

print('\n# small primes using the aks test')
print([p for p in range(101) if aks_test(p)])

그리고 출력은 다음과 같습니다.

# p: (x-1)^p for small p
  0: +1
  1: -1 +1x^1
  2: +1 -2x^1 +1x^2
  3: -1 +3x^1 -3x^2 +1x^3
  4: +1 -4x^1 +6x^2 -4x^3 +1x^4
  5: -1 +5x^1 -10x^2 +10x^3 -5x^4 +1x^5
  6: +1 -6x^1 +15x^2 -20x^3 +15x^4 -6x^5 +1x^6
  7: -1 +7x^1 -21x^2 +35x^3 -35x^4 +21x^5 -7x^6 +1x^7
  8: +1 -8x^1 +28x^2 -56x^3 +70x^4 -56x^5 +28x^6 -8x^7 +1x^8
  9: -1 +9x^1 -36x^2 +84x^3 -126x^4 +126x^5 -84x^6 +36x^7 -9x^8 +1x^9
 10: +1 -10x^1 +45x^2 -120x^3 +210x^4 -252x^5 +210x^6 -120x^7 +45x^8 -10x^9 +1x^10
 11: -1 +11x^1 -55x^2 +165x^3 -330x^4 +462x^5 -462x^6 +330x^7 -165x^8 +55x^9 -11x^10 +1x^11

# small primes using the aks test
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top