여부 POW (a, b) %의 B == C에서

Question

제가

POW가 (a, b) % B는

를 == 여부를 확인하고 싶은 (오버플로 없음)

은 2 ≤ b ≤ 32768 (2)이고 2 ≤ a ≤ b이고 a와 b는 정수임.

그러나 b가 큰 숫자 인 pow(a, b) % b을 직접 계산하면 C가 빠르게 오버플로됩니다. 이 조건이 성립 하는지를 확인하는 트릭/효율적인 방법은 무엇입니까?

이 질문은 Fermat의 작은 정리에 대한 증인을 찾는 것을 기반으로합니다.이 정리는 Fermat의 작은 정리가 거짓이면 b가 소수가 아님을 나타냅니다.

또한 걸리는 시간이 제한되어 있으므로 너무 느려서는 안됩니다 (2 초 또는 그 이상). 가장 큰 Carmichael 번호 인 소수 b은 소수가 아니지만 을 2 <= a <= b (b < = 32768)으로 만족하지 않습니다. 따라서 pow(a, b) % b == a을 2 <= a <= 29341으로 확인하는 방법이 너무 느려서는 안됩니다.

Answer 1

Exponentiation by squaring 방법을 사용할 수 있습니다.

아이디어는 다음 바이너리 형식으로

• 분해 b하고 제품을 우리가 항상 32768 이하 %b를 사용
• 공지 사항을 분해하기 때문에 발생합니다 32 비트 수에 항상 적합 .

그래서 C 코드는 다음과 같습니다

으로

/* 
* this function computes (num ** pow) % mod 
*/ 
int pow_mod(int num, int pow, int mod) 
{ 
    int res = 1 

    while (pow>0) 
    { 
     if (pow & 1) 
     { 
      res = (res*num) % mod; 
     } 
     pow /= 2; 
     num = (num*num)%mod; 
    } 

    return res; 
} 

Answer 2

Z/bZ에서 모듈러 산술 연산을 수행하고 있습니다.

참고하는 몫환에서 요소의 클래스의 n 번째 전력 소자의 n 승의 클래스이기 때문에, 우리는 다음과 같은 결과가 :

(a^b) mod b = ((((a mod b) * a) mod b) * a) mod b [...] (b times) 

을 그래서, 당신은 큰 정수 라이브러리가 필요하지 않습니다.

당신은 단순히 다음의 알고리즘 (의사 코드)를 사용하여 C 프로그램을 작성할 수 있습니다

• 정수로 변수 a와 b를 선언합니다.
• a로 초기화되는 임시 변수 temp를 사용하십시오.
• b 단계가있는 루프를 수행하고 각 단계에서 (temp * a) mod b을 계산하여 새 임시 값을 얻습니다.
• 결과를 a와 비교하십시오. 이 공식으로

, 당신은 온도의 최대 값은 32768입니다 것을 볼 수 있습니다, 그래서 당신은 저장 온도에 정수를 선택할 수 있습니다.