이 무작위 소수 테스트 알고리즘의 복잡성을 어떻게 개선합니까?

Question

숫자가 소수 일 경우 1을 반환하고 합성 일 경우 0을 반환하는 다음 프로그램을 작성했습니다. 복합체를 프라임으로 잘못 식별 할 가능성이 있지만 다음 알고리즘의 시간 복잡도를 개선 (감소)하는 것에 대한 제안 사항이 필요합니다.

int compute(int n) 
{ 
    int x; 
    for(int i = 1; i < 100 * sqrt(n); i++) 
    { 
     x = rand() % ((int)sqrt(n) + 1); 
     if(x != 0 && x != 1 && x!=n) 
     { 
      if(n % x == 0) 
      return 0; 
     } 
    } 
    return 1; 
} 

Answer 1

Miller-Rabin primality test을 살펴볼 수 있습니다. 이 테스트에서는 일련의 "감시"값을 사용하고 계산을 수행합니다. 각각의 증인 계산은 "합성"또는 "가능성이 소수"의 결과를 제공합니다. k 증인 을 사용하고 모두 "가능한 소수"결과를 주면 그 수가 실제로 일 확률은 1/4^k입니다.

런타임은 O (k 로그^3 n)이며 이는 O (sqrt (n)) 알고리즘보다 상당히 개선 된 것입니다.