Численные методы решения ЗАДАЧИ О МАТЕМАТИЧЕСКИЙ СЕЙФ
Ключевые слова:
математический сейф, конечные кольца, конечные поля, системы линейных уравненийАннотация
Рассматриваются алгоритмы, необходимые для построения расширений полей вычетов: тест Рабина для проверки полиномов на несводимость, построение таблиц сложения и умножения по модулю неприводимого полинома, вычисления противоположного и обратного элементов на основе этих таблиц. Описываются особенности нумерации элементов конечных полей и ее влияние на эффективность выполнения базовых операций над элементами поля. Предлагается алгоритм построения базиса множества решений систем линейных уравнений и алгоритм построения общего решения системы неоднородных уравнений над конечным полем. Все алгоритмы имеют полиномиальные оценки временной сложности, которые приведены в таблицах для конкретных примеров систем линейных уравнений и различных параметров алгоритмов. Рассматривается применение предложенных алгоритмов решения систем линейных уравнений к задаче о математическом сейф. Рассмотрена адаптация этой задачи в поле. Описаны различные случаи представления математического сейфа, условия существования решения, алгоритмы решения задачи в этих случаях и их эффективность на поле, рассматривается. Указаны возможные применения систем уравнений над полем в кодировке и криптографии.
