Обратный элемент в кольце по модулю(инверсия в криптографии)

@John Locke · Регистрация: 09.05.2014

Author24 — интернет-сервис помощи студентам

Доброго времени суток. Имеется функция ,которая реализует обобщенные алгоритм Евклида. т.е. находит НОД(a,b) и числа x,y, такие
что $https://www.cyberforum.ru/cgi-bin/latex.cgi?a*x+b*y=gcd(a,b)$ (gcd - наибольший общий делитель).Так вот вопрос, как с помощью этого алгоритма реализовать инверсию? т.е найти число $https://www.cyberforum.ru/cgi-bin/latex.cgi?d={c}^{-1}mod m$

C++

void evklid(long long a, long long b)
   {
    long long q,x,lastx,y,lasty,temp,temp1,temp2,temp3;
    
    if (b>a) {
        temp=a; a=b; b=temp;
    }
    
    x=0;
    y=1;
    lastx=1;
    lasty=0;
    while (b!=0) {
        q= a/b;         
    cout << "q =  " << q << endl;
        temp1= a%b; 
        a=b;      
        b=temp1; 
 
               temp2 = x; 
        x=lastx-q*x;            
        lastx = temp2;  
        
        temp3 = y;
        y = lasty-q*y;
        lasty=temp3;
    }
    cout << "ОТВЕТЫ:\n"<<endl;
    cout << "НОД= " << a << endl;
    cout << "x=" << lastx << endl;
    cout << "y=" << lasty << endl;
    }

	11.11.2015, 19:43