소수성 테스트

-2

가능한 중복 :
Fastest primality test 소수성 테스트

누군가가 숫자의 소수성을 결정하기위한 효율적인 알고리즘을 줄 수 있습니까?

많은 수의 소수성을 테스트 할 때 기존의 반복 방법은 많은 시간이 걸리는 것처럼 보입니다. 확률 론적 알고리즘을 시도했지만 정확도에 만족하지 못했습니다.

2011-11-15 Vijeenrosh P.W

내가 아는 한, 당신은 소수 테스트를 사용할 때 정확성과 효율성 사이에서 항상 균형을 유지할 것입니다. 나는 [Miller Rabin primality test] (http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)만을 사용했지만, 당신이하고있는 일에 더욱 정교해야한다고 생각합니다. – Lucas

또한, 충분히 큰 k를 선택하십시오. 2^-k (또는 n> 1에 대한 n^-k)는 지수 적으로 빠르게 빠릅니다 (읽기 : 매우 빠름). –

와우, 그보다 훨씬 더 많은 중복이 있습니다 - 소수 검사를 검색하십시오. – Cascabel

가장 유용한 확률 론적 소수 검사는 Rabin-Miller primality test (implementation in C)입니다. 이것은 RSA가 사용하는 것입니다.

결정 론적 테스트는 속도가 필요하고 실제 응용 프로그램에서는 거의 유용하지 않은 경우 더 어렵습니다.

출처

2011-11-15 18:34:06 Dennis

소수성 테스트

답변

관련 문제