РЕШЕНИЕ БОЛЬШИНСТВА ЛИНЕЙНЫХ ЛОГИЧЕСКИХ УРАВНЕНИЙ НЕСОВМЕСТНОЙ СИСТЕМЫ НА СУПЕРКОМПЬЮТЕРЕ

Abstract

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