Приложение. Корни и степени

В настоящем приложении мы описываем два алгоритма, необходимые для реализации методов разложения на множители и тестов на простоту, представленных в этой книге. Алгоритм первого параграфа вычисляет целую часть квадратного корня данного положительного целого числа, в то время как алгоритм § П.2 предназначен для вычисления степеней в арифметике остатков.

§ П.1. Квадратные корни

Оба алгоритма разложения на множители из третьей главы используют вычисление квадратных корней. В настоящем параграфе мы описываем процедуру, вычисляющую целую часть квадратных корней натуральных чисел. Это в точности то, что требуется для алгоритма деления методом проб из § 3.2. Кроме того, алгоритму Ферма нужна процедура выяснения, является ли данное натуральное число полным квадратом. Но полный квадрат, только если Так что алгоритм этого параграфа может быть использован и при решении последнего вопроса.

Метод состоит в вычислении такой убывающей последовательности натуральных чисел

что в момент ее стабилизации для некоторого к 0) мы получаем искомую целую часть: Последовательность определяется рекуррентной формулой:

при Идея заключается в том, что начиная с последовательность будет уменьшаться вплоть до Рассмотрим следующие утверждения:

Таким образом, каждое из натуральное число, не превосходящее Следовательно, эта последовательность может иметь лишь конечное число членов. В частности, найдется некоторый номер для которого В этом случае из утверждения (3) получим:

Итак, нам осталось доказать три выписанных утверждения. Заметим, что если вещественные числа, то Таким образом, утверждение (1) будет следовать из неравенства: Но последнее неравенство мгновенно получается из следующих выкладок:

Для доказательства (2) заметим, что, по определению последовательности, Поскольку целое число, то неравенство влечет Возводя в

квадрат обе части последнего неравенства, получаем Поэтому откуда

Чтобы доказать третье утверждение, предположим, что что эквивалентно неравенствам

Отсюда

Значит, и одновременно Но из последнего неравенства следует, что Поэтому

что равносильно равенству

Описанный метод вычисления целой части квадратного корня легко представить в виде алгоритма.

Алгоритм квадратных корней

Ввод: целое число

Вывод: целая часть квадратного корня из

Шаг 1. Начинаем с присвоений: и переходим к шагу 2.

Шаг 2. Бели то останавливаемся и выписываем в противном случае переходим к шагу 3.

Шаг 3. Заменяем значение X на текущее значение У, а переменной присваиваем значение и возвращаемся к шагу 2.

§ П.2. Алгоритм степеней

Предположим, что нам даны три натуральных числа Здесь мы описываем алгоритм определения вычета степени по модулю Для более эффективной работы алгоритма полезно представить показатель в двоичной системе счисления:

где коэффициенты могут принимать значения О или 1. Таким образом,

Заметим, что может быть равно 1 (если или а (если Обозначив через получаем

Теперь положим Тогда

Продолжая начатую процедуру, мы определяем последовательность целых чисел где Конечно, поскольку мы делаем вычисления с элементами из нам надлежит находить вычет всех произведений по модулю на каждом шаге алгоритма.

Обратите внимание на то, что на каждом этапе мы либо возводим в квадрат число, либо вычисляем произведение для Более того, если на каком-то шаге нам попалось нулевое значение нам совершенно не нужно вычислять

На практике представление показателя в двоичной системе счисления происходит одновременно с вычислением степени. Так, например, если нечетно, то в противном

случае, Аналогично, основываясь на четности или нечетности числа

можно определить значение Заметьте, что выписанная сумма равна одному из следующих отношении: если четно, и если оно нечетно. Формализованный алгоритм выглядит следующим образом:

Алгоритм степеней

Ввод: целые числа а, ей где Вывод: вычет степени по модулю

Шаг 1. Начинаем с присвоений:

Шаг 2. Если то выводим сообщение: в противном случае переходим к шагу 3.

Шаг 3. Если нечетно, то присваиваем переменной вычет произведения по модулю значение после чего перегодим к шагу 5; в противном случае идем к шагу 4.

Шаг 4. Если четно, то присваиваем значение и идем к шагу 5.

Шаг 5. Заменяем текущее значение переменной А на вычет по модулю и переходим к шагу 2.