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

Впрочем, это определение не учитывает величины чисел, участвующих в вычислениях.Алгоритм вычисления ad mod m.Вычислим r - остаток от деления числа a на b, a = bq+r, 0 ( r < b.Сложность теоретико-числовых алгоритмов.Положим a0 = a и затем для i = 1,…,r вычислим ai ( a2i-1adi (mod m) .В общем виде дихотомический алгоритм позволяет вычислить n-ю степень в моноиде.Ясно, что число итераций, необходимых для выполнения алгоритма, зависит только от показателя n.Если r = 0, то b есть искомое число.Полиномиальные алгоритмы в теории чисел - большая редкость.если повезёт, быстро приводит к требуемому результату.