1
갑자기 두 가지 유형의 Miller Rabin 소수 테스트 방법이 발생했습니다. 하나는 uses randoms이고 다른 하나는 does not use randoms입니다.밀러 라빈의 소수성 검사는 두 가지 유형이 있습니까?
숨겨진 임의 생성이 두 번째 내부에 있습니까? 고맙습니다.
A
답변
2
두 번째 것은 Miller-Rabin 소수 검사의 deterministic variant입니다. 대신 임의의 숫자에서 발생하는 "증거"번호를 사용하는 충분한 것으로 알려진 소수의 목록 대신 사용됩니다 수 n 테스트 할
이 모두 < 2 (LN n을 시도, 작은) 2는 필요하지 않습니다. 잠재 성 증인의 훨씬 작은 세트가 충분하다고 알려져 있기 때문에 "
n < 3,825,123,056546413051이면 a = 2, 3, 5, 7, 11, 13, 17, 19, 및 23.
이것은 alist에있는 연결된 소스 코드의 소수입니다.
+0
대단히 감사합니다. –
대단히 감사합니다. 확률 적 알고리즘이 훨씬 더 빠르다는 것과 왜 결정 론적 알고리즘이별로 인기가 없는지를 이해할 수있는 양 항복의 간단한 비교. –
결정 론적 M-R 테스트는 사람들이 그것에 대해 모르기 때문에 주로 덜 인기가 있습니다. 특히 더 최적의 세트를 사용하면이 크기에 대한 확률 테스트를 사용하여 신뢰할 수있는 결과를 얻는 데 필요한 것보다 적은 수의 테스트로 모든 64 비트 입력에 대해 매우 효율적인 결정 론적 답변을 얻을 수 있습니다. 실제로 올바른 결과를 얻지 않는 한 실제로는 더 빠릅니다. – DanaJ
예 .. 결정론적인 MR과 제곱근 경계 법을 비교하는 것에 대한 연구를 여기에서했습니다. https://isuramanchanayake.wordpress.com/2016/12/08/algorithms/#graphical-comparison. 거기서 나는 det-MR이 큰 입력에 대해 훨씬 낫다는 것을 알았고 10 이하의 값에 대해서는별로 효율적이지 못했습니다^12 –