Регистрация / Вход
Прислать материал

Универсальные методы решения линейных систем над конечными полями на экзафлопных вычислителях

Докладчик: Замарашкин Николай Леонидович

Должность: Старший научный сотрудник, кандидат физико-математических наук

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

Основные планируемые результаты проекта:
1.1 Разработка оптимального по сложности универсального численного метода решения больших разреженных систем линейных уравнений над конечными полями с большим числом элементов (порядка 10^150).
1.2 Разработка оптимального по сложности универсального численного метода решения больших разреженных систем линейных уравнений над полем GF(2).
1.3 Создание оптимальных по сложности универсальных алгоритмов решения линейных систем, реализующих разработанные методы, на различных вычислительных системах с пиковой производительностью 100 и более Tflops.
1.4 Разработка массивно-параллельных методов для ускорения вычислительно трудоемких блочных операций.

2.1 Разрабатываемый универсальный численный метод решения линейных систем над конечными полями с числом элементов порядка 10^150 предназначается для систем
1) с матрицей системы размера не менее 10^7
2) средним числом ненулевых элементов в строке не более 150 с допустимым отклонением ± 10%.

2.2 Разрабатываемый универсальный численный метод решения линейных систем над конечным полем GF(2) предназначается для решения линейных систем:
1) с матрицей системы размера не более 2·10^9
2) средним числом ненулевых элементов в строке не более 1000 с допустимым отклонением ± 20%.

2.3 Разрабатываемые массивно-параллельные методы для ускорения вычислительно трудоемких блочных операций предназначаются для работы с блоками следующих размеров:
1) от 6 400 до 64 000 для конечного поля GF(2),
2) от 100 до 1000 для конечных полей с числом элементов порядка 10^150

3. Идея универсального алгоритма уникальна и была предложена ранее одним из членов коллектива (М.А. Черепнев). Создание единого алгоритма, реализация которого может быть одновременно эффективной как на вычислительных системах с быстрыми коммуникациями так и на системах с медленными коммуникациями, по нашему мнению, является новой. Преполагается, что с помощью разрабатываемого программного обеспечения будут обновлены мировые рекорды в задачах анализа ключей современных систем шифрования.

4. На сегодняшний день для решения больших разреженных систем над конечными полями используются, по сути, два подхода: блочные методы типа Ланцоша и блочные методы типа Видемана-Копперсмита. Оба подхода имеют недостатки. Простота методов типа Ланцоша нивелируется их ограниченным параллельным ресурсом. С другой стороны высокоэффетивные методы типа Видемана-Копперсмита весьма непросты в программировании и предъявляют жесткие требования к вычислительным системам, например к объему общей памяти. Разрабатываемый в проекте универсальный алгоритм лишен обоих недостатков.

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

Назначение и область применения, эффекты от внедрения результатов проекта:
1. Решение больших систем линейных уравнений связано в первую очередь с анализом стойкости современных систем шифрования данных. К системам над большими полями приводит задача дискретного логарифмирования, а к системам над полем GF(2) задача разложения составного числа на два простых множителя, которая является основой для системы шифрования RSA.

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

Текущие результаты проекта:
4.1 Проведен анализ существующих современных методов и вычислительных технологий, связанных с задачами решения больших разреженных систем над конечными полями.
4.2 Разработан универсальный численный метод решения больших разреженных систем линейных уравнений над конечными полями с большим числом элементов (порядка 10^150).
4.3 Разработан универсальный численный метод решения больших разреженных систем линейных уравнений над полем GF(2).