왜 primes를 샘플링하는 두 가지 방법이 똑같이 오래 실행됩니까?

Question

그래서 저는 작은 RSA 알고리즘을 구현했으며 그 과정에서 큰 소수를 찾는 함수를 작성했습니다.
먼저 소수성을 테스트하는 prime? 함수를 작성한 다음 두 가지 버전의 프라임 검색 함수를 작성했습니다. 첫 번째 버전에서는 소수를 칠 때까지 임의의 BigIntegers를 테스트합니다. 두 번째 버전에서는 임의의 BigInteger를 샘플링 한 다음 소수점을 찾을 때까지 증가시킵니다. 이 코드를 실행

(defn resampling [] 
    (let [rnd (Random.)] 
    (->> (repeatedly #(BigInteger. 512 rnd)) 
     (take-while (comp not prime?)) 
     (count)))) 

(defn incrementing [] 
    (->> (BigInteger. 512 (Random.)) 
     (iterate inc) 
     (take-while (comp not prime?)) 
     (count))) 

(let [n 100] 
    {:resampling (/ (reduce + (repeatedly n resampling)) n) 
    :incrementing (/ (reduce + (repeatedly n incrementing)) n)}) 

는 증분 함수 리샘플링 기능에 대한 310.74 332.41 두 평균을 수득 하였다.
이제 첫 번째 숫자가 나에게 완벽합니다. prime number theorem은 n의 소수가 약 n*ln(n) (여기서, ln은 자연 로그)이라는 것을 나타냅니다. 따라서 인접한 소수 간의 거리는 약 n*ln(n) - (n-1)*ln(n-1) ≈ (n - (n - 1))*ln(n) = ln(n)입니다 (큰 값이 nln(n) ≈ ln(n - 1) 인 경우). 512 비트 정수를 샘플링하기 때문에 소수 사이의 거리가 ln(2^512) = 354.89 부근에있을 것으로 기대합니다. 따라서 무작위 추출은 프라임을 치기 전에 평균적으로 약 354.89 번의 시도가 필요하다.
저를위한 수수께끼는 왜 증가 기능이 다만 많은 단계를 취하는 지입니다. 소수가 355 단위 떨어져있는 그리드에서 다트를 던지는 것을 상상해 보면, 평균적으로 두 개의 소수 사이의 중심을 치고 있기 때문에 다음 상위 높은 소수로 걸어가는 데 평균적으로 많은 단계가 소요됩니다.

은 (prime?의 코드는 조금 긴 것입니다. 당신은 here 좀 걸릴 수 있습니다.)

Answer 1

당신은 소수 똑같이 경우로하지 보인다, 배포한다고 가정합니다. 소수는 항상 예를 ​​10...01 및 10...03 다음 다음 쌍 2*ln(n)에 와서에 대한 쌍으로 올 줄 경우

는 이제 다음과 같은 가능한 시나리오를 생각해 보자. 샘플링 알고리즘의 경우이 분포는 차이가 없지만 증가 알고리즘의 경우 해당 쌍 내부에서 시작할 확률은 거의 0이므로 평균적으로 큰 거리의 절반 즉, ln(n)이 필요합니다.

간단히 말해서 증분 알고리즘의 동작을 평가하려면 오른쪽 사이의 평균 거리를 알아야합니다.