Математические основы защиты информации. Ишмухаметов Ш.Т - 26 стр.

Глава 1. Системы шифрования с открытым ключом                        27

       b       1   1   0   0   0   1     1   1
        c      2   8 64 84 35 444 93 247

Ответ: 2199 mod 1003 = 247.

      Приведем здесь еще один вариант алгоритма быстрого возведения
в степень, не требующий предварительного перевода степени в двоичное
представление:

long powm(long a, long b, long n) {
      long c = 1;
      while (b) {
        if (b%2 == 0)
            { b/ = 2; a = (a ∗ a)% n;}
        else
            { b − −; c = (c ∗ a)% n;}
        }
      return c;
}


2.7. Генерация простых чисел. Решето Эратосфена.
      Очевидно, что любое простое число, не равное 2, является нечетным.
Существуют признаки делимости целых чисел на различные простые числа,
например, чтобы число в десятичном виде делилось на 3 и 9 достаточно,
чтобы сумма его цифр делилась на 3 и 9 соответственно. Чтобы число
делилось на 5, достаточно, что его последняя цифра была 0 или 5.
      Такие частные признаки делимости можно использовать, если нужно
уменьшить множество кандидатов проверки на простоту или отсечь заведомо
составные числа. Альтернативным способом получения простых чисел
является решето Эратосфена, приписываемое древнегреческому ученому
Эратосфену Киренскому, жившему примерно в 276 - 194 г. до н.э.
      Для нахождения множества простых до заранее выбранной верхней
границы B мы сначала выписываем последовательность всех нечетных чисел