3

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

1 ответ 1

7

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

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

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;
}
4
  • можно пояснить пожалуйста
    – OneOrigiN
    15 сен 2018 в 16:06
  • Ну, я примерно расписал. Более-менее понятно? Еще раз - ВСЕ умножения выполняются по модулю 899, т.е., например, 308*308 = 94864 = 899*105+469, так что 308 в квадрате по модулю 899 равно 469. А быстрое возведение в степень - см., например, тут.
    – Harry
    15 сен 2018 в 16:11
  • Вы дали мне наводку,а я разобрался с помощью вас,википедии и листка с карандашом...Вы умные но иногда не внимательны :)
    – OneOrigiN
    15 сен 2018 в 16:25
  • а лучше подключить библиотеку gmp, созданную специально для "длинной" арифметики
    – magrif
    15 сен 2018 в 16:48

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.