Каникулы

СПАА Семинар уходит на каникулы, заседания продолжатся в сентябре, следите за новостями в нашем канале.

Также теперь есть группа @spaagroup. Там можно писать комментарии к семинарам, обмениваться полезной информацией и задавать вопросы по алгебре, теории чисел и их приложениям.

24 сентября 2025 г., 18:00 МСК, онлайн

Эффективные алгоритмы построения невырожденных квазициклических матриц

Виктория Владимировна Высоцкая, сотрудница кафедры ИБ ВМК МГУ имени М.В. Ломоносова

Яндекс Телемост->

Доклад мотивирован задачей поиска перспективного варианта постквантовой схемы электронной подписи. Среди всех схем на кодах, исправляющих ошибки, конструкции на основе квазициклических кодов выделяются своей высокой эффективностью с точки зрения хранения ключевой информации. В ряде таких схем существенным шагом алгоритма генерации ключей является построение невырожденной двоичной квазициклической матрицы. Эту задачу можно решать классическими методами, не учитывающими внутреннюю структуру матриц, либо специализированными подходами, как, например, было сделано в схеме LEDAcrypt. В последнем случае циклическая подматрица сопоставляется многочлену, и исходная задача сводится к построению невырожденной матрицы в кольце многочленов. Однако предложенный алгоритм имеет экспоненциальную сложность.

В докладе будет развита идея, предложенная в LEDAcrypt: работа будет вестись с матрицами многочленов и производными от них вспомогательными матрицами. Будет разобрана связь между свойствами невырожденности матриц всех этих типов. Дадим определение обратимой матрицы в кольце многочленов и покажем, что обратимость в этом случае эквивалентна невырожденности. Также будет продемонстрирована невозможность применения в кольце алгоритма гауссового исключения и будет предложена его альтернатива. В завершение будут описаны специализированные алгоритмы построения невырожденных квазициклических матриц, которые существенно используют циклическую структуру и обеспечивают лучшие на сегодняшний день оценки трудоемкости.

Начинаем семинар:
Яндекс Телемост->

8 октября 2025 г., 18:00 МСК, онлайн

Анализ и синтез линейных и нелинейных преобразований для использования в XSL-схемах

Степан Андреевич Давыдов, кафедра ИБ ВМК МГУ имени М.В. Ломоносова

Яндекс Телемост->

Работа посвящена задачам анализа и синтеза линейных и нелинейных преобразований, используемых в XSL-схемах. XSL-схемы являются одним из основных способов построения блочных шифрсистем и функций хэширования, используемых в криптографии.

Для нелинейных преобразований (S-блоков) предложен метод синтеза дифференциально 4-равномерных подстановок чётных размерностей, обладающих максимально известной нелинейностью. Найдены классы преобразований, допускающих применение данного метода. Построенные подстановки обладают относительно высокими показателями алгебраической степени, степени нелинейности и графовой алгебраической иммунности.

Для циркулянтных и рекурсивных линейных преобразований предложены подходы к эффективной программной реализации. В частности, найдены разложения указанных матриц через суммы и произведения матриц, обладающих эффективной реализацией. Для матрицы линейного преобразования шифрсистемы Кузнечик показано, что указанные разложения обладают хорошими соотношениями скорости шифрования - используемой памяти и могут быть эффективны на низкоресурсных устройствах.

В части анализа XSL-схем рассмотрен метод инвариантных подпространств применительно к шифрсистемам, использующим рекурсивные и циркулянтные матрицы. Полностью описаны инвариантные подпространства максимально рассеивающих циркулянтных матриц. Указанный результат справедлив для матриц, используемых в шифрсистеме AES и хэш-функции Whirlpool. Для рекурсиных матриц показано отсутствие инвариантных подпространств определённого вида, согласованного с размером S-блока. Результат справедлив для матрицы линейного преобразвания шифрсистемы Кузнечик.

Начинаем семинар:
Яндекс Телемост->

22 октября 2025 г., 18:00 МСК, онлайн

CayleyPy — методы искусственного интеллекта в теории групп и графов

Александр Викторович Червов, к.ф.-м.н, Institut Curie

Яндекс Телемост->

В докладе будет представлена основанная на методах ИИ открытая Python-библиотека CayleyPy, которая способна работать с графами Кэли очень больших размеров. CayleyPy значительно превосходит классические системы компьютерной алгебры GAP/SAGE в решении ряда задач, с её помощью были получены сотни гипотез и несколько результатов в области теории групп и графов. Классические задачи теории групп (например, разложение элементов группы) можно переформулировать как задачи обучения с подкреплением и решать их способами аналогичными AlphaGo/Zero от Google Deepmind.
Также будет дан обзор различных последних достижений в формирующейся области "ИИ для математики" / "AI for math".

Доклад опирается на работы:
— A. Chervov et al., CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version), 2025. https://arxiv.org/abs/2509.19162
— A. Chervov et al., CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs, 2025. https://arxiv.org/abs/2502.18663
— A. Chervov et al., A Machine Learning Approach That Beats Large Rubik's Cubes, 2025. https://arxiv.org/abs/2502.13266

Начинаем семинар:
Яндекс Телемост->

5 ноября 2025 г., 18:00 МСК, онлайн

Методы построения кодов, исправляющих ошибки, с помощью программирования в ограничениях

Григорий Андреевич Трофимюк, к.т.н., старший научный сотрудник лаборатории теории информации и кодирования Университета ИТМО

Яндекс Телемост->

Рассматривается задача построения двоичных линейных блоковых кодов с улучшенными дистантными свойствами. Обозреваются алгебраические методы и методы компьютерного поиска. В частности, рассматривается построение кодов при помощи решателей задач программирования в ограничениях. Демонстрируется применение этих методов для поиска коротких кодов с наилучшим известным минимальным расстоянием и улучшенной корректирующей способностью.

Начинаем семинар:
Яндекс Телемост->

19 ноября 2025 г., 18:00 МСК, онлайн

Криптографические свойства булевых функций

Николай Александрович Коломеец, к.ф.-м.н., научный сотрудник лаборатории криптографии Математического центра в Академгородке, г. Новосибирск

Яндекс Телемост->

Доклад затронет особенности применения булевых (и векторных булевых) функций в криптографических приложениях. Будут рассмотрены основные классы криптографических функций, подходы к построению функций с "хорошими" свойствами, а также наиболее известные открытые вопросы в данной области.

Начинаем семинар:
Яндекс Телемост->

3 декабря 2025 г., 18:00 МСК, онлайн

Функциональные непрерывные дроби и результаты рекордного типа в гиперэллиптических полях

Максим Максимович Петрунин, к.ф.-м.н., старший научный сотрудник НИИСИ РАН

Яндекс Телемост->

Доклад включает краткое введение в теорию функциональных непрерывных дробей в гиперэллиптических полях, а также обзор результатов рекордного типа, связанных с двумя классическими нерешёнными задачами: о кручении в Якобианах гиперэллиптических кривых и о периодичности квадратного корня. Полученные оценки и конструкции основаны на сочетании глубокой теории и интенсивных компьютерных вычислений.

Начинаем семинар:
Яндекс Телемост->