모듈화 지수를 단순화하십시오. C++

RSA 암호화 시스템의 암호 해독 기능을 작성 하려는데 숫자가 매우 작음 수가 적지 만 출력이 정확하지 않을 수 있습니다. 부동 소수점 에러 또는 어떤 종류의 스택 오버 플로우).모듈화 지수를 단순화하십시오. C++

문제를 일으키는 프로세스는 (11^23) mod 187로 단순화 될 수 있지만 누군가가보고 싶어 할 경우 전체 코드가 포함됩니다. Simon Singh 박사 ("Wolfram Alpha"사용 확인)의 "The Code Book"부록 J에 사용 된 예제이므로 대답은 88이어야합니다. 그러나, 나는 149의 결과를 얻는다. 그러나, 숫자가 작을수록 Wolfram Alpha와 일치한다.

내 생각 I이 기술을 사용하여 멱승 잉여를 단순화해야한다는 것을 :

^B = A^C *는^D [여기서 C + D = B]

그러나

, I 이 문제가 100 % 확실하지 않다면, 이것은 처음으로 스택 오버플로입니까? (나는 아직도 그 의미가 100 % 확실하지 않다). 누군가가 나에게 가려고하기 전에 어떤 숙제도 아니며이 질문이 사소한 것으로 여겨지면 미안합니다. 모든 사람들이 이렇게하기가 어려울 것이라고 생각한다면 gmp.h를 사용하고 있습니다.하지만 전적으로 정직하다면 오히려하지 않을 것입니다. 내 코드는 아래에 있습니다 (전반부는 개인 키를 계산하는 것입니다. 개인 키는 내가 갖고있는 문제와 관련이 없지만 잘못 입력 한 경우를 대비해 포함 시켰습니다.) 정말 도움이 될 수 있기를 바랍니다. 감사합니다. 너는 대단히 사전에.

#include <iostream> 
#include <math.h> 

using namespace std; 

unsigned int modinv(unsigned int u, unsigned int v) 
{ 
    unsigned int inv, u1, u3, v1, v3, t1, t3, q; 
    int iter; 

    u1 = 1; 
    u3 = u; 
    v1 = 0; 
    v3 = v; 

    iter = 1; 

    while (v3 != 0) 
    { 

     q = u3/v3; 
     t3 = u3 % v3; 
     t1 = u1 + q * v1; 

     u1 = v1; v1 = t1; u3 = v3; v3 = t3; 
     iter = -iter; 
    } 

    if (u3 != 1) 
     return 0; 
    if (iter < 0) 
     inv = v - u1; 
    else 
     inv = u1; 
    return inv; 
} 

int main() 
{ long unsigned int p = 17; 
long unsigned int q = 11; 
long unsigned int phi = (p-1)*(q-1); 
long unsigned int e = 7; 
long unsigned int c = 11; 
long unsigned int n = p*q; 
long unsigned int d = modinv (e,phi); 
    { 
     cout << fmod (pow (c, d), n); 
    } 
    return 0; 
}

출처

2014-02-26 Michael

아마도 11^n mod 187은 11이 주 요소 (187 = 11 x 17) 중 하나이기 때문에 나쁜 사례일까요? 따라서 n> = 1 인 경우 11^n mod 187의 경우 16 개의 값만 반복되는 패턴으로 나타납니다. 11 121 22 55 44 110 88 33 176 66 165 132 143 77 99 154 || 11 121 .... 그래서 11^n mod 187 = 11^(1 + ((n-1) mod 16)) mod 187. – rcgldr

나는 그것을 정렬했다 :)'pow' 함수는 자연수가 아닌 부동 소수점을 사용한다. 어쨌든 덕분에 멋지게 일한 내 자신의 모듈러 지수를 쓸 수 – Michael

11^23은 대략 2^80입니다. 2^53까지의 정수만 이중 부동 소수점 수로 정확하게 나타낼 수 있습니다. 따라서 fmod (pow (c, d), n))는 근사값을 반환합니다. 그건 암호화에 적합하지 않습니다.

ADDED 반복 된 제곱을 사용하여 모듈러 지수를 수행 할 수 있습니다. 기사 유클리드 알고리즘에 대한 링크가 포함 중국 잉여 알고리즘에 대한 링크가 포함되어

RSA decryption worked example

참고 :

출처

2014-02-26 22:45:10 user515430

무엇이 적절한 대안이 될 것이라고? – Michael

모듈화 된 지수 함수를 구현하십시오. 그것은 당신의 modinv보다 적은 수의 라인을 필요로하는 것은 상당히 직설적이다. – user515430

기존의 방법이 없으므로 직접 작성해야합니까? 죄송 합니다만 이것이 바보 같은 질문 인 것 같습니다. – Michael

는 RSA에 대한이 위키의 문서 섹션 도움이 될 것 "제곱으로 지수화"에 대한 위키 백과의 기사를 확인 : 주어진 두 개의 소수 p와 q는 두 개의 정수 a와 b를 찾아 ap + bq = 1이되도록 또한 (ap) mod q == 1과 (bq) mod p == 1을 의미합니다. 명확하지 않은 것은 a 또는 b가 음수이고 음수 값이 나머지 알고리즘의 첫 번째 부분에서 사용된다는 것입니다 (기사에서는 유클리드 알고리즘의 값을 사용한다고 명시합니다). 예를 들어, a가 음수이면 mod p == 1이지만 ((a + q) p) mod q도 == 1이므로 a와 a + q는 모두 p의 역으로 간주 될 수 있습니다. 수학적으로 q를 구하십시오.

출처

2014-02-27 03:03:25 rcgldr

모듈화 지수를 단순화하십시오. C++

답변

관련 문제