Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ

Abstract

Рассматривается операция умножения больших чисел, от быстродействия которой зависит быстродействие ассиметричной криптографии. Приведено детальное описание алгоритма реализации операции умножения N-разрядных чисел на основе вычисления N-разрядных БПФ с использованием операций “распаковки” и “упаковки”. Описана процедура, позволяющая строить более простой алгоритм с использованием только формул “распаковки” или только формул “упаковки”.