Основы аналитической теории чисел

Быстрые вычисления с целыми числами и полиномами

Его легко доказать индукцией по k. Поскольку числа a и b взаимно просты, имеем r = 1, и это доказывает, что алгоритм действительно даёт решение уравнения ax by = 1. Буквой мы обозначили количество делений с остатком, которое в точности такое же, как и в алгоритме Евклида. Полиномиальные алгоритмы в теории чисел – большая редкость. Да и оценки сложности алгоритмов чаще всего опираются на какие-либо не доказанные, но правдоподобные гипотезы, обычно относящиеся к аналитической теории чисел. Для некоторых задач эффективные алгоритмы вообще не известны. Иногда в таких случаях всё же можно предложить последовательность действий, которая, «если повезёт», быстро приводит к требуемому результату. Существует класс так называемых вероятностных алгоритмов, которые дают правильный результат, но имеют вероятностную оценку времени работы. Обычно работа этих алгоритмов зависит от одного или нескольких параметров. В худшем случае они работают достаточно долго. Но удачный выбор параметра определяет быстрое завершение работы. Такие алгоритмы, если множество «хороших» значений параметров велико, на практике работают достаточно эффективно, хотя и не имеют хороших оценок сложности. 3. Полиномиальная арифметика Рассмотрим вероятностный алгоритм, позволяющий эффективно находить решения полиномиальных сравнений по простому модулю.