Deprecated

Данная реализация имеет существенные ограничения в использовании, кроме того в данном коде плохо реализована многопоточность. В связи с этим рекоммендуется использовать актуальную реализацию алгоритма, размещённую здесь.

Генератор неприводимых многочленов над полем GF[2] (степени от 1 до 63)

Данная программа реализует алгоритм Берлекампа проверки неприводимости многочленов. Получение неприводимого многочлена выполняется путём генерации случайных многочленов с последующей проверкой их на неприводимость. Первый же найденный неприводимый многочлен возвращается.

Ограничения

Программа будет работать только на компьютерах с архитектурой AMD64 и ARM64 (т.к. требуется поддержка 64-битных чиесл). Компиляция возможна только с помощью GCC или Clang (т.к. используется макрос __builtin_clzll) с поддержкой C++ 17. Также необходимо наличие библиотеки POSIX Threads (т.к. на её основе выполняется распараллеливание генератора). Для компиляции желательно наличие Cmake (т.к. проект удобнее всего собирать именно с помощью него).

Использование

Необходимо подключить #include "Generator.hpp" и вызвать Generator::GetIrrPoly(degree), где degree – степень требуемого неприводимого многочлена (от 1 до 63). Результирующий многочлен имеет тип uint_fast64_t, т.е. представлен 64-битным числом. В этом числе каждый бит содержит значение коэффициента многочлена при соответствующей номеру бита степени x. Например многочлен P2 = x^2 + 1 будет представлен числом 0b0...0101.

Если требуется проверка отдельно взятого многочлена на неприводимость необходимо подключить #include Polynomial.hpp и вызвать Polynomial(p).IsIrredusible(), где p - число типа uint_fast64_t, кодирующее проверяемый многочлен. В результате вернётся булевое значение, говорящее о приводимости (false) или неприводимости (true) данного многочлена. Проверка отдельных многочленов выполняется в один поток, таки образом она не требует наличия библиотеки POSIX Threads, остальные ограничения сохраняются.

Для компиляции готового кода при наличии установленных make и cmake достаточно выполнить make debug или make release в корневой папке проекта для получения и запуска соответствующей сборки.

Документация

Документация кода программы сгенерирована с помощью Doxygen и может быть найдена в папке docs или на соответствующей странице GitHub Pages. Незадукомментированные возможности:

в файле main.cpp находится код приведённого ниже бенчмарка, для его активации необходимо дописать #define TIMINGS в начале файла.
если перед подключением #include "Random.hpp" в файле Generator.cpp добавить #define PARFENOV_PLEASE, то вместо генератора псевдослучайных чисел из стандартной библиотеки будет использоваться генератор, реализованный самостоятельно. Этот генератор точно перебирает все числа, имеющиее число значащих бит не более требуемого. Тем не менее, начальным значением всегда является 1, таким образом при каждом запуске генератор будет возвращать одну и ту же последовательность.

Для обновления документации при наличии установленных make и doxygen достаточно выполнить make docs в корневой папке проекта.

Бенчмарк

Для тестирования скорости работы программы был выполнен запуск проверки всех многочленов заданной степени на неприводимость. (Проверялись только многочлены, старший и младший коэффициенты которых отличны от нуля, т.к. остальные многочлены очевидно приводимы). Проверка выполнялась в одном потоке на компьютере с CPU Intel Core i7 2.6 Ghz и RAM 16 GB 2133 MHz LPDDR3. Были выполнениы расчёты для степеней от 2 до 33 включительно. Результаты бенчмарка можно найти в файле timings.txt. Результаты представлены в следующем виде:

deg: степень проверяемых многочленов
num: число найденных неприводимых многочленов данной степени
mic: общее время выполнения проверки в микросекундах
mil: общее время выполнения проверки в миллисекундах
sec: общее время выполнения проверки в секундах
min: общее время выполнения проверки в минутах
hou: общее время выполнения проверки в часах

Следует отметить, что результаты проверки многочленов до 11 степени совпадают с таблицей многочленов, приведённой в двухтомнике "Конечные поля" авторов Лидл Р., Нидеррайтер Г. Результаты для более высоких степеней проверялись выборочно. В результате проверок ошибок в работе алгоритма найдено не было.

Отказ от ответственности

Код программы создан на основе ранее выполненной реализации, а также статьи "A Formalization of Berlekamp’s Factorization Algorithm" авторов Jose Divason, Sebastiaan Joosten, Rene Thiemann, Akihisa Yamada. В реализации могут (с очень малой вероятностью) присутствовать ошибки. Тем не менее, данное программное обеспечение распространяется под лицензией MIT, поэтому автор не несёт ответственности за возможные ошибки и их последствия, а также не планирует их самостоятельного исправления.