О синтезе компьютерных программ алгебраических операций и преобразований в конечных полях

摘要

Рассматриваются два способа автоматического синтеза программ умножения многочленов над конечным полем по методу Карацубы: аналитический, имитирующий построение функциональной схемы умножения, и способ, основанный на использовании рекурсивного описания метода Карацубы, а также способы автоматического синтеза программ приведения произведения по модулю многочлена малого веса и возведения многочлена в степень характеристики поля. Символьным сравнением результатов действия синтезированных программ доказывается их функциональная эквивалентность. Такой же подход возможен при синтезе программ умножения в кольце целых чисел и простом поле, а также при синтезе программ дискретного преобразования Фурье и преобразования Уолша-Адамара и др.