RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. вопр. криптогр.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


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

Эта публикация цитируется в 1 научной статье (всего в 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)$. Предел вероятности распознавания несовместности для этого алгоритма такой же, как для алгоритма полного перебора. Доказательства используют геометрические свойства случайной системы уравнений.

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

DOI: https://doi.org/10.4213/mvk17

Полный текст: PDF файл (832 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.212.2
Получено 22.IV.2010

Образец цитирования: А. В. Шаповалов, “Характеристики случайных систем дискретных уравнений при неравновероятной выборке неизвестных”, Матем. вопр. криптогр., 1:3 (2010), 93–117

Цитирование в формате AMSBIB
\RBibitem{Sha10}
\by А.~В.~Шаповалов
\paper Характеристики случайных систем дискретных уравнений при неравновероятной выборке неизвестных
\jour Матем. вопр. криптогр.
\yr 2010
\vol 1
\issue 3
\pages 93--117
\mathnet{http://mi.mathnet.ru/mvk17}
\crossref{https://doi.org/10.4213/mvk17}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mvk17
  • https://doi.org/10.4213/mvk17
  • http://mi.mathnet.ru/rus/mvk/v1/i3/p93

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. В. Шаповалов, “Совместность случайных систем уравнений с неравновероятной выборкой двузначных неизвестных”, Матем. вопр. криптогр., 2:4 (2011), 109–146  mathnet  crossref
  • Математические вопросы криптографии
    Просмотров:
    Эта страница:211
    Полный текст:101
    Литература:22
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020