a в степени d по модулю n. Длинная арифметика.

[Alex_FF]

Необходимо реализовать программу для шифрования и расшифрования сообщений криптосистемой RSA.
Что дано: Сообщение; ключ.

Проблема: как вычислить a^d (mod n), если a, d и n - длинные числа (около 500 десятичных цифр). Нужен алгоритм, который вычисляет это за приемлемое время. При этом никакими библиотеками для работы с длинными числами пользоваться нельзя.

Я писал раньше программу для работы с длинными числами, и вот что у меня имеется: умножение длинного на короткое, умножение длинного на длинное, деление с остатком длинного на короткое, деление с остатком длинного на длинное, сложение/вычитание длинных чисел.

+ знаю алгоритм быстрого возведения в степень для чисел базовых типов (напр. Int32).

[LeBron]

Кто мешает реализовать быстрое возведение в степень с длинынми числами? Если брать кажый раз по модулю, то не будут получатся числа, больше n. Если 500 цифр, то двоичный логарифм d примерно 1500. Значит всего 1500 итераций. Если десятичных цифр 500, то можно хранить по 9 разрядов под 8байтовым типом - и получится менее 60 цифр. Даже если предположить очень кривую реализацию и 5 операций в каждой итерации (2 умножения, 2 модуля и 1 деление длинного на короткое), то имеем 15 тысяч условных операций в итерации. С учетом пооперанной реализации - примерно 50 тысяч. Если подумать над тем, будет ли польза при таких маленьких числах от Карацубы/Винограда/Штрассена/Фурье, то может даже еще быстрее получится (асимптотика там пониже, только весь выиграш константа перекроет).
В итоге - 75 миллионов операций. Надо быстрее? Что для Вас приемлимое время?

[Alex_FF]

LeBron,
вот, к примеру, алгоритм для не длинных чисел:

long powmod(long a, long d, long n)
{
    long b = 1;

    while (d) 
    {
        if (d % 2 == 0) 
        {
             d /= 2;
             a = (a * a) % n;
        }
        else 
        {
             d--;
             b = (b * a) % n;
         }
     }
     return b;
}

Если у меня a, d, n - длинные числа, т. е. массив, то, чтобы только проверить условие в цикле [while(d)] на это уже нужно sizeof(d) операций + нужно постоянно делить это d на 2, брать то a, то b по модулю n... думаю это будет висеть сутки. Или не будет?

[LeBron]

Сообщение от Alex_FF

LeBron,
вот, к примеру, алгоритм для не длинных чисел:

long powmod(long a, long d, long n)
{
    long b = 1;

    while (d) 
    {
        if (d % 2 == 0) 
        {
             d /= 2;
             a = (a * a) % n;
        }
        else 
        {
             d--;
             b = (b * a) % n;
         }
     }
     return b;
}

Если у меня a, d, n - длинные числа, т. е. массив, то, чтобы только проверить условие в цикле [while(d)] на это уже нужно sizeof(d) операций + нужно постоянно делить это d на 2, брать то a, то b по модулю n... думаю это будет висеть сутки. Или не будет?

??? Это как надо проверять? Проверка "число больше 0" состоит из 2 условий - "количество цифр в числе больше 1" или "последняя цифра числа не 0". Делить на 2 и брать по модулю - я уже написал выше примерные рассчеты. Даже при весьма кривых руках и весьма убитом компе - минута. В идеале - подозреваю, что можно уложится в секунду (но это надо еще в теории покопаться). Примерно секунд 10 должно хватить с запасом.