확률이 높은 소수의 근원 증명

확률 론적 버전의 Miller-Rabin 검정을 사용하여 중간 크기 (200-300 자릿수)의 가능성있는 소수 목록을 생성했습니다. 그러나 가능성이 충분하지 않습니다! 나는 을 알고을 알고이 숫자들은 소수입니다. 파이썬에서 wrapped 나 wrappable이 가능한 라이브러리가 있습니까? 더 효율적인 primality 증명 알고리즘 중 하나를 구현하고 있습니까? 내가 찾을 수있는확률이 높은 소수의 근원 증명

또는 아는 사람 않는 명확, 자세한하고, 사전 지식의 큰 거래를 가정하지 않는 ECPP (또는 유사 빠른 알고리즘)의 완벽한 설명?

업데이트 : 다른 테스트 인 APRT-CLE의 Java implementation을 찾았습니다.이 테스트는 소수성을 입증합니다. 그것은 원자 프로세서에서 10 분 안에 291 자리 소수 후보를 확인했습니다. 아직도 더 빠른 것을 희망하지만 이것은 유망한 시작처럼 보입니다.

출처

2011-01-20 senderle

읽은 ECPP에 대한 설명이 명확하지 않거나, 상세하거나, 완전하지 않거나 사전 지식이 너무 많습니다. "선행 지식"에 대한 귀하의 표준이 어쩌면 될지 모릅니다. 지금까지 시도한 것에 대한 배경 지식을 제공하십시오. –

파이썬 라이브러리가 필요 하겠지만 Java 메소드를 체크 아웃하는 것을 고려해 보았습니다. http://download.oracle.com/javase/1.4.2/docs/api/java/math/BigInteger.html#isProbablePrime(int) ? 나는 그들이 Miller-Rabin 알고리즘을 구현한다고 생각하며, 최대 500 자리 숫자에 대한 나의 개인적인 경험으로부터는 매우 정확합니다. –

사실, 저는 이미 파이썬에서 구현 된 Miller-Rabin 알고리즘을 가지고 있습니다 - 쉽고 편하고 놀라 울 정도로 빠릅니다. 그러나 나는 조금 더 확신을 원한다. (또는 당신이 어떻게 보느냐에 따라 무한히 많다.) – senderle

신뢰할 수있는 다항식 소수 테스트를 제공하는 알고리즘으로 AKS을 고려하십시오. 알고리즘의 구현과 표현을 참조하는 older SO article이 있습니다.

출처

2011-01-20 20:58:09

흥미 롭다. 나는 그것을 살펴볼 것이다. 내 이해는 그것이 가장 빠른 테스트는 아니지만, 아마도 내 크기 범위의 숫자에 대해 충분히 빠릅니다. 감사! – senderle

@sendle : 이것이 단지 근사는 아니며 입증되지는 않았지만 널리 알려진 가정 (예 : Riemann 가설)에 의존하지 않는다는 점에서 이것이 완전히 신뢰할 수있는 유일한 테스트라는 것도 이해합니다.). –

@Martin v. Löwis : 논란의 여지가 없지만 [wikipedia는 동의하지 않는 것으로 보입니다] (http://en.wikipedia.org/wiki/AKS_primality_test) : "ECPP와 APR은 주어진 숫자가 소수임을 증명하거나 증명하지 않습니다. 모든 입력에 대해 다항식 시간 범위를 갖는 것으로 알려져 있지 않습니다. " 아직도, 위키 백과는 틀린 것으로 알려져 있습니다. – senderle

저는 Pari/GP 라이브러리와 언어가 APR-CL을 사용하여 소수성을 증명한다는 사실을 발견했습니다. 실제로이 크기 범위의 숫자에 대해 선호되는 알고리즘입니다. GP는 원자 프로세서에서 20 초 이내에 291 자리의 후보 프라임을 증명합니다. 이는 내 요구에 충분하며, c 유형을 사용하여 액세스 할 수있는 라이브러리가 제공됩니다.

import ctypes 

def pari_isprime(self, n): 
    try: pari = ctypes.cdll.LoadLibrary("libpari.so") 
    except OSError: 
     print "pari_isprime: couldn't load libpari!" 
     exit() 
    int(n) 
    pari.pari_init(4000000, 2) 
    ret = bool(pari.isprime(pari.gp_read_str(str(n)))) 
    pari.pari_close() 
    return ret

또한 instant 모듈을 사용할 수도 있습니다.

상기

from instant import inline 

runpari_code = """ 
PyObject* runpari(PyObject *args) { 
    pari_init(40000000, 2); 
    char *pari_code; 
    char *outstr; 

    if (!PyArg_Parse(args, "s", &pari_code)) { return NULL; } // instant uses old-style args; for a module, use PyArg_ParseTuple 
    outstr = GENtostr(gp_read_str(pari_code)); 
    pari_close(); 
    return Py_BuildValue("s", outstr); 
} 
""" 
runpari = inline(runpari_code, system_headers=['pari/pari.h'], libraries=['pari'])

또한 적절한 CPython의 확장을 기초로 사용될 수있다 : 여기 PARI의 파서를 통해 문자열을 실행하고 결과를 문자열로 반환하는 간단한 C 함수이다.

출처

2011-01-22 22:11:22 senderle

확률이 높은 소수의 근원 증명

답변

관련 문제