Для сложности умножения в стандартном базисе поля GF(2n), где п = 2.3k, получены оценка сложности умножения 5n log3 n log2 log3 л + 0(п log n) и оценка сложности инвертирования, которая больше указанной асимптотически в 2,5 раза. Как следствие, для сложности умножения двоичных многочленов степени N справедлива верхняя оценка (10 + o(l))N log3 N log2 log N. Указанные оценки обобщаются на случай других конечных 'полей. Для случая, когда n = (р — 1) рk, где р — такое простое число, что 2 есть первообразный корень по модулю р и 2Р-1 — 1 не кратно р2, для стандартного базиса в поле GF(2n) построены мультиплер сложности (С + о(1))(n log3 n log2 log n) и инвертор сложности О (log р)n log n log log n, где С ≦ 10. Работа выполнена при поддержке РФФИ, проекты 11-01-00508 и 11-01-00792-а, и программы фундаментальных исследований Отделения математических наук РАН ?Алгебраические и комбинаторные методы математической кибернетики и информационные системы нового поколения?, проект ?Задачи оптимального синтеза управляющих систем?.
展开▼
机译：为了在GF（2N）字段的标准基础上乘法的复杂性，其中获得了5N log3 n log2 log3l + 0（n log n）的乘法的复杂性并评估了复杂性反转的反转，这更为指定渐近2.5倍。结果，对于程度n的二元多项式乘法的复杂性，上部估计（10 + o（l））n log3 n log2 log n有效。在其他有限“字段的情况下总结了这些估计。对于n =（p-1）pk的情况，其中p是简单的数字，2是模块p和2p-1 - 1不是多个p2的主要根，在gf字段中标准基础（2n）构建复杂性乘数（C + O（1））（n log3 n log2 log n）和复杂性逆变器O（log p）n log n log log n，其中with≤10.RFBR，项目支持11-01-00508和11-01-00792 -A，以及俄罗斯科院数学科学分支机构的基础研究计划吗？数学漫字学和新一代信息系统的代数和组合方法，项目？问题对控制系统的最佳合成吗？
展开▼
