| Название НИОКТР |
Алгебраические подходы к проблемам оптимизации алгоритмов, сложности вычислений и защиты информации
|
| Аннотация |
Проект направлен на применение и развитие алгебраических методов для построения и оптимизации эффективных
алгоритмов обработки данных, исследования вычислительной сложности практически важных алгоритмических проблем, создания новых методов защиты информации и изучение их криптостойкости.
Многие практически важные алгоритмические проблемы эффективно сводятся к проблемам решения уравнений в
конечных алгебраических системах: графах, группах, полугруппах, полях, булевых алгебрах и т.д. Для исследования
этих проблем в последние 30 лет в научной школе В.Н.Ремесленникова было создано новое направление -
универсальная алгебраическая геометрия. Применение подходов и методов универсальной алгебраической геометрии
позволяет по-новому взглянуть на исходные алгоритмические проблемы и получить более эффективные алгоритмы
для их решения. В проекте планируется изучение вычислительной сложности проблем решения уравнений в
различных алгебраических системах, разработка более эффективных классических, а также приближенных и
генерических алгоритмов для них. Приближенные алгоритмы выдают решение, близкое в некотором смысле к
оптимальному. Генерические алгоритмы решают проблему для “почти всех” или случайных входов.
Также планируется изучение вычислительной сложности в алгебраических системах. Одной из центральных
нерешенных проблем информатики является проблема о совпадении классов вычислительной сложности P и NP. Для
произвольной алгебраической системы можно определить аналоги этих классов с помощью машин, которые
моделируют алгоритмы в этой системе (например, так называемые машины Блюм-Шуба-Смейла). Естественно
возникает вопрос о совпадении P и NP в данной системе. Для некоторых конкретных систем было доказано
неравенство P=/=NP. В проекте предполагается обобщить эти разрозненные результаты и, с использованием понятий и
методов универсальной алгебраической геометрии, доказать неравенство P=/=NP в широком классе алгебраических
систем. Кроме того, планируется получение нелинейных нижних оценок на сложность алгебраических схем в
некоторых алгебраических системах. Для этого предполагается развить классический метод Штрассена, использовав
понятие размерности в произвольных алгебраических системах, предложенное в 2014 г. в работе В.Н.Ремесленникова,
А.Г.Мясникова и Э.Ю.Данияровой. Это позволит применять метод Штрассена, который работает только в полях, для
других алгебраических систем.
В области методов защиты информации, планируется изучение криптостойкости систем шифрования и
криптографических алгоритмов. Классического подхода к обоснованию криптостойкости современных систем
шифрования недостаточно, так как то, что для взлома не существует эффективного (полиномиального) алгоритма еще
не значит, что эту систему можно применять на практике. Дело в том, что при реальном использовании системы в
начале каждого сеанса происходит генерация ключей - входа для алгоритмической проблемы взлома. Для этой
проблемы взлома может не существовать полиномиального алгоритма, решающего ее для всех входов, но может
существовать полиномиальный алгоритм, решающий ее для “почти всех” входов, то есть генерический полиномиальный
алгоритм. Этот алгоритм будет взламывать систему с вероятностью, близкой к единице. Таким образом, проблема
взлома должна быть трудна и генерически. В проекте планируется провести генерический анализ некоторых новых
систем шифрования, а также некоторых известных алгоритмических проблем с целью возможности их применения в
криптографии.
|
| Доступ к ОКОГУ исполнителя |
False
|
| Количество связанных РИД |
0
|
| Количество завершенных ИКРБС |
0
|
| Сумма бюджета |
21000.0
|
| Дата начала |
2025-08-19
|
| Дата окончания |
2027-12-30
|
| Номер контракта |
25-11-20023
|
| Дата контракта |
2025-05-21
|
| Количество отчетов |
1
|
| УДК |
512.54
|
| Количество просмотров |
15
|
| Руководитель работы |
Трейер Александр Викторович
|
| Руководитель организации |
Миронов Андрей Евгеньевич
|
| Исполнитель |
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ ИМ. С.Л. СОБОЛЕВА СИБИРСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК
|
| Заказчик |
Российский научный фонд
|
| Федеральная программа |
Отсутствует
|
| Госпрограмма |
—
|
| Основание НИОКТР |
Грант
|
| Последний статус |
2025-10-10 12:03:07 UTC, 2025-10-10 12:03:07 UTC
|
| ОКПД |
Работы оригинальные научных исследований и экспериментальных разработок в области естественных и технических наук, кроме биотехнологии
|
| Отраслевой сегмент |
—
|
| Минздрав |
—
|
| Межгосударственная целевая программа |
—
|
| Ключевые слова |
теория графов; генерическая сложность; алгебраическая сложность вычислений; алгебраическая криптография; алгебраические системы; системы уравнений
|
| Соисполнители |
—
|
| Типы НИОКТР |
Фундаментальное исследование
|
| Приоритетные направления |
—
|
| Критические технологии |
—
|
| Рубрикатор |
27.45.17 - Теория графов; 27.17.17 - Группы; 27.03.17 - Алгоритмы и вычислимые функции
|
| OECD |
—
|
| OESR |
Прикладная математика; Общая математика
|
| Приоритеты научно-технического развития |
а) переход к передовым технологиям проектирования и создания высокотехнологичной продукции, основанным на применении интеллектуальных производственных решений, роботизированных и высокопроизводительных вычислительных систем, новых материалов и химических соединений, результатов обработки больших объемов данных, технологий машинного обучения и искусственного интеллекта;
|
| Регистрационные номера |
—
|
