Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень

Обчислення значень многочленів.Множення числа В на число А зводиться до обчислення.Тепер ми повинні ще раз скористатися цим алгоритмом для обчислення АВ (mod N) .Зведення модуль многочлен множення.Цей метод особливо ефективний при апаратній реалізації алгоритмів.Дуже зручно відмовитися від операцій множення і ділення та замінити їх операціями додавання.Метод полягає в наступному.Оскільки , то ділення у кільці лишків виконується зі складністю .Щоб відрізняти арифметичну складність від бітової в оцінках ми використовуватимемо символи і .І буде шуканим значенням многочлена.