RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические вопросы криптографии // Архив

Матем. вопр. криптогр., 2010, том 1, выпуск 3, страницы 93–117 (Mi mvk17)

Эта публикация цитируется в 1 статье

Характеристики случайных систем дискретных уравнений при неравновероятной выборке неизвестных

А. В. Шаповалов

Лаборатория ТВП, Москва

Аннотация: Изучается случайная система дискретных уравнений $S$ относительно $n$ неизвестных, состоящая из $M=M(n)$ уравнений. Каждое уравнение содержит не более $m$ неизвестных, которые выбираются случайно, независимо и, вообще говоря, неравновероятно. Указаны условия, при которых предельное при $M-c\sqrt n=o(\sqrt n)$, $n\to\infty$, $m=\operatorname{const}$ значение вероятности совместности случайной системы уравнений непрерывно убывает от $1$ до $0$ с ростом $c$ от $0$ до $\infty$. Построен алгоритм распознавания несовместности случайной системы уравнений, имеющий трудоемкость $O(\sqrt n)$. Предел вероятности распознавания несовместности для этого алгоритма такой же, как для алгоритма полного перебора. Доказательства используют геометрические свойства случайной системы уравнений.

Ключевые слова: системы дискретных уравнений, неразрешимость, вероятностные алгоритмы.

УДК: 519.212.2

Получено 22.IV.2010

DOI: 10.4213/mvk17



© МИАН, 2024