C 함수는 잘못된 int 값인

Question

을 반환하므로 C와 같은 모양의 모듈러 함수를 얻었습니다. m, E의 값을 인쇄 할 때

int modexp(int m, int e, int n) 
{ 
    printf("%i\n", m); 
    printf("%i\n", e); 
    printf("%i\n", n); 
    printf("\n"); 

    if(e == 0) 
    { 
     return 1; 
    } 
    if(e%2 == 1) 
    { 
     return modexp(m, e-1, n) * m%n; 
    } 
    else 
    { 
     int modTemp = modexp(m, (int)(e/2), n); 
     modTemp = modTemp * modTemp; 
     return modTemp % n; 
    } 
} 

나는이

int p = 3511; 
printf("%i\n", modexp(2, p-1, p*p)); 

처럼 내 main() 함수에서 호출하고있는 n은 나는 결국 = 0을 전자까지 올바른 재귀 값을 가져 . 함수가 1을 반환해야하는 경우입니다. 예상 된 정수 1 대신 코드의 해당 위치에 확실히 반환되지만, -6593454가 발생하고 이유를 알 수 없습니다.

전체 코드

는 여기에서 찾을 수 있습니다 : https://gist.github.com/anonymous/7024ac77b2432a381968

모든 입력이 매우 감사합니다 ... 당신의 숫자가 넘쳐

Answer 1

m 비트 값으로 n 비트 값을 곱하면 (n + m) 비트 결과가 생성됩니다. 그래서 modexp(m, e-1, n) * m 및 modTemp * modTemp이 오버플로됩니다. 당신은 32 비트

return ((int64_t)modexp(m, e-1, n) * m) % n; 
... 
int64_t modTemp = modexp(m, (int)(e/2), n); 
modTemp = modTemp * modTemp; 
return modTemp % n; 

Answer 2

, 당신의 숫자가 MOSTE 가능성이 32 또는 64 비트가 여기에 정수를 체결한다. 즉, 최대 크기는 2^31=2147483648 또는 2^63= 9223372036854775807 일 수 있습니다. modexp(...)에 m%n을 곱한 크기 만 보시면됩니다. 그것은 꽤 많은 수의 :

가

같은이 modTemp * modTemp

Answer 3

1에 간다 실제로 때 e == 0 반환하지만이 반환 값은 재귀 이전 수준에 만든 계산의 용어입니다. 이 같은 코드를 수정하는 경우 :

#include <stdio.h> 
int modexp(int m, int e, int n) 
{ 
    printf("%i\n", m); 
    printf("%i\n", e); 
    printf("%i\n", n); 
    printf("\n"); 

    if(e == 0) 
    { 
     printf("returning 1\n"); 
     return 1; 
    } 
    if(e%2 == 1) 
    { 
     int tmp=modexp(m, e-1, n) * m%n; 
     printf("returning %d\n",tmp); 
     return tmp; 
    } 
    else 
    { 
     int modTemp = modexp(m, (int)(e/2), n); 
     modTemp = modTemp * modTemp; 
     modTemp= modTemp % n; 
     printf("returning %d\n",modTemp); 
     return modTemp;; 
    } 
} 


int main(){ 
    int p = 3511; 
    printf("%d\n", modexp(2, p-1, p*p)); 
    return 0; 
} 

당신은 끝이 출력을 얻을 것이다 :

returning 1 
returning 2 
returning 4 
returning 8 
returning 64 
returning 4096 
returning 8192 
returning 5473259 
returning 10946518 
returning 2217782 
returning 5855618 
returning 11711236 
returning 8916378 
returning 5505635 
returning -1026672 
returning 975519 
returning 1951038 
returning 195330 
returning 390660 
returning -6593454 
-6593454 

이는 1 e == 0에 대해 반환 추가 계산에 사용되는 것을 보여줍니다.

어느 시점에서 코드가 int으로 오버플로되므로 결국 음수를 얻습니다. 당신은 아마 더 긴 유형을 사용해야합니다.

Answer 4

나는 그것이 modTemp 변수의 오버 플로우의 동의를 값에서 전체 64 비트 결과를 얻기 위해 확대 곱셈이 필요합니다. 그러나 명확히하기 위해 modTemp의 형식을 int에서 long으로 변경하고 다음과 같이 b/e/m을 사용하여 m/e/n을 변경하는 것이 좋습니다.

#include <stdio.h> 

int modexp(int b, int e, int m); // b: base; e: exp; m: modulus 


int main() 
{ 
    int p = 3511; // given number p 
    printf("%i\n", modexp(2, p-1, p*p)); // last line printed is the remainder of mod exp 
} 


int modexp(int b, int e, int m) 
{ 
    printf("%i\n", b); 
    printf("%i\n", e); 
    printf("%i\n", m); 
    printf("\n"); 

    if(e == 0) 
    { 
     return 1; 
    } 
    if(e%2 == 1) 
    { 
     return modexp(b, e-1, m) * b%m; 
    } 
    else 
    { 
     long modTemp = modexp(b, (int)(e/2), m); // !!here modTemp is declared as long!! 
     modTemp = modTemp * modTemp; 
     return modTemp % m; 
    } 
}