Data_Structures_and_Algorithms

САКОД

2 Factormod

Факторизация полиномов над конечным полем 2
NB - Обязательное использование метода Жордана Гаусса - приводящего к матрице вида RREF.
В ином случае, вычисление собственных векторов матрицы без вида RREF приведет к комплексным числам (очевидно)
В дальнейшем код будет переписан на язык Python.
Текущий алгоритм раскладывает СВОБОДНЫЕ от квадратов полиномы - не реализован алгоритм SQFF
Пример ввода:
Если имеется полином вида: x^5 + x^4 + 1
То входные данные будут: 5 4 0 (записываем только позиции на которых есть единицы)
Для особо умных, которые считают "раз конечное поле 2" то все математические операции будут как в Булевой алгебре
Прошу обратиться с местный ВУЗ на кафедру математики для получения два и дальнейшего отстранения от работы
Для тех - кто действительно хочется разобраться:
1x^5 + 1x^4 + 0x^3 + 0x^2 + 0x^1 + 1x^0 (расписали факториал x^5 + x^4 + 1 наглядно)
прибавив единицу (то есть 1x^0) - получим: 1x^5 + 1x^4 + 0x^3 + 0x^2 + 0x^1 + 2x^0
НО не забудьте после этого применить mod(2) для каждого коэффициэнта
То есть, финальный результат - 1x^5 + 1x^4 + 0x^3 + 0x^2 + 0x^1 + 0*x^0
Распишем без X ниже:
110001 + 1 = 110000
Операции сложения и умножения над конечным полем != операции сложения и умножения в булевой алгебре
В Булевой алгебре мы представляем числа в двоичной системе
В конечном поле Галуа 2 число 1 - максимальное и существуют только 0 и 1