308 в степени 611 mod 899

#cpp #алгоритм #математика #шифрование #rsa

Как вычислить значение настолько "большого" выражения, как 308^611 (mod 899).
Просто делаю алгоритм RSA на C++. Возможно, решение в mod n, но я не понимаю? как
это сделать.
    

Ответы

Ответ 1

Просто выполняете умножения по модулю, а для возведения в степень используете быстрое
возведение в степень.

Рассмотрим ваш случай. 

689 = 1010110001

Значит, 308 в 689 степени считается так (все действия по модулю 899).

308^2 = 469
308^4 = 469^2 = 605
308^8 = 605*605 = 132
308^16 = 132*132 = 343   

16 степень соответствует второй справа единице в бинарном представлении, так что
теперь множим 343 на 308 и получаем 461 - это 308 в 17 степени по модулю 899.

Дальше получаем 308^32, перемножая 343*343, умножаем на наше 461... Ну, и так далее.
Идея понятна?

Примерно так это выглядит на C++:

unsigned long long iqpow(unsigned long long x,
                         unsigned long long e,
                         unsigned long long p)
{
    unsigned long long res = 1;

    for(x %= p;e;e>>=1)
    {
        if (e&1) res = (res*x)%p;
        x = (x*x)%p;
    }
    return res;
}

int main()
{
    cout << iqpow(308,611,899) << endl;
}