Операция умножения в поле чисел Отложенный перенос ООО «Сайфер ЛТД», к.т.н. Влад Ковтун Андрей Охрименко

Содержание Актуальность Существующие алгоритмы Общее описание подхода Идея отложенного переноса Сравнение производительности Выводы 2

Введение Цель: повышение производительности операции умножения целых чисел посредством отложенного переноса Объект: процесс умножения целых чисел Предмет: механизм переноса переполнения из старшего разряда 3

Актуальность 4

Алгоритмы умножения «В столбик» Рекурсивный Карацубы-Офмана* Шёнхаге Штрассена (Дискретное преобразование Фурье) Алгоритм Фюрера (развитие Шёнхаге Штрассена ) Comba* и другие * Применимы для криптографических задач 5

Подходы к повышению производительности Увеличение разрядности машинных слов Использование специализированных потоковых команд процессоров (MMX, SSE, SSE2, SSE3, SSE4, SSE5) Распараллеливание (многопоточность) Совершенствование алгоритмов Совершенствование структур данных 6

Алгоритм Comba 7

Алгоритм Comba: Сложность 8

Алгоритм Comba: Структура 9

Алгоритм Comba: Недостатки Во вложенных циклах п. 2.1 и п. 3.1 происходит накопление суммы с переносом в 32-х разрядных временных переменных, п , и п , Отметим, что в этом случае, происходит 3 операции сложения 32-х разрядных целых (две из них с учетом переноса), 3 присвоения 32-х разрядных переменных. Накопление суммы с учетом переноса производится на каждой итерации цикла 2.1. Во вложенных циклах п. 2.1 и п. 3.1 при накоплении суммы учитываются переносы, используя вставки на языке ассемблера, что в свою очередь не позволяет выполнять спаривание и распараллеливание таких операций, как следствие – неэффективное использование ресурсов процессора. Высокая внутренняя связность, в связи с учетом переносов, не дает возможности эффективно распараллелить циклы п. 2 и п. 3. Не учитывается возможность использования современными процессорами поддержки 64-х разрядных операций. 10

Усовершенствования Избавиться от последовательного переноса – изменение порядка вычислений: Использование 32-х и 64-х данных для накопления переносов Применение переносов по необходимости Распараллелить не связанные вычисления: Цикл накопления суммы произведений 11

Алгоритм Modified Comba 12

Алгоритм Modified Comba: Сложность 13

Алгоритм Modified Comba 14

Алгоритм Modified Comba 15

Алгоритм Modified Comba: Преимущества Современные 32-х разрядные процессоры эффективно реализуют операции сложения 32-х и 64-х разрядных целых чисел, используя 64-х либо 32-х разрядные команды и переменные. Это позволяет реализовать накопление переноса в результате сложения 32-х разрядных значений в 64-х разрядной переменной, что избавит от необходимости после каждого сложения, выполнять учет и корректировку переноса. Накопленный перенос будет учитываться на финальных итерациях цикла п. 2 и п. 3. Современные процессоры обладают многоядерной архитектурой, что позволяет им параллельно выполнять несколько потоков команд. Это позволяет выполнить итерации циклов п. 2 и п. 3 параллельно используя реализацию OpenMP. 16

Библиотеки Целочисленной арифметики: 17 CLN CryptoPP GNU MP LiDIA MIRACL NTL OpenSSL PIOLOGIE MUNTL TinyECC MPFQ GFA BBNUM FLINT LibTom: TomsFastMath

Библиотеки Наилучшие показатели у GMP* В GMP используется алгоритм умножения Карацубы Дальнейшее сравнение будет с GMP 4.1.2, скомпилированной с помощью Microsoft Visual Studio.NET (Win32, Max Speed, SSE2) Тестовое приложение на Microsoft Visual C (Win32, Max Speed, SSE2) Среднее для 1 млн. операций * Ashraf Abusharekh and Krzysztof Gaj. Comparative Analysis of Software Libraries for Public Key Cryptography 18

Библиотеки Modified Comba скомпилирован с помощью Microsoft Visual С (Max Speed, SSE2) Тестовое приложение на Microsoft Visual C (Max Speed, SSE2) Среднее для 1 млн. операций * Ashraf Abusharekh and Krzysztof Gaj. Comparative Analysis of Software Libraries for Public Key Cryptography 19

Тестовые поля 20 ПолеПростое число GF(p82) GF(p164) GF(p192) GF(p224) GF(p256) GF(p320) GF(p384) GF(p521) * Поля рекомендованные NIST для ECC

Замеры производительности 21 Процессор Операционная система Ядер Потоков выполнения команд Примечание Intel Pentium Dual Core E5400 Microsoft Windows XP (x86) 22 Intel Core i3 M350 Microsoft Windows 7 (x64) 24With Hyper Threading

Замеры производительности 22 ПолеВремя, мкс Core i3Pentium Dual Core Comba*CombaGMP4.1Comba*CombaGMP4.1 GF(p82) 0,075 0,120 0,1210,06870,1190,125 GF(p164) 0,21 0,393 0,40,2090,3630,407 GF(p192) 0,276 0,393 0,410,2890,3630,414 GF(p224) 0,343 0,69 0,5490,3640,590,522 GF(p256) 0,422 0,875 0,6380,4560,7440,648 GF(p320) 0,6973 1,278 0,970,6861,0530,969 GF(p384) 0,961 1,75 1,380,941,451,36 GF(p521) 1,63 2,8 2,6631,4862,412,643

Выводы 1. Предложенный в работе подход отложенного переноса, позволяет добиться увеличения производительности программной реализации алгоритма умножения целых чисел Comba, в 1,5-2 раза, а также превзойти производительность популярной математической библиотеки GMP 4.1.2, в среднем в 1,5 раз. 2. Алгоритм умножения Modified Comba, является предпочтительнее алгоритма Карацубы, используемого в GMP, т.к. программная реализация алгоритма умножения Modified Comba оказалась быстрее, реализации алгоритма Карацубы в GMP, для современных аппаратных платформ (32-х и 64-х бит). 3. Механизм отложенного переноса позволяет применить различные техники распараллеливания к алгоритму Modified Comba, например OpenMP. 23

Вопросы? Спасибо за внимание! 24

ООО «САЙФЕР ЛТД» Владислав Ковтун www: