Цитата:
многочлен разбивается на 2 части - степени

и

Мне кажеться что у вас тут опечатка, ведь

нам неподходит.
______________
Смотрите как я понял, если немного затронуть алгоритм, то там

соответственнно справа в моём равенстве мне

надо разсматривать тоже

.
И второе уточнение, получаеться что когда мы получили уже урезаные полиномы, то чтобы проверить равенство мне достаточно будет посмотреть равны ли коефициенты при степенях, или лучше изначально проводить данные сравнения в

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

, так как

(это они говорят на 3 странице). Тогда если выполнять ещо и данное сравнение

раз, то сложность у алгоритма получаеться нехилая.