Optimisation of big N-width digits multiplication based on N-width DFT
Abstract
It is considered multidigit multiplication, that has biggest influence on asymmetric cryptography performance. It is given detailed description of N-digit multiplication algorithm that is based on FFT of the length of N using of "unpacking" and "packing" formulas. It is given description, that gives possibility to build more simpler algorithm with using only either "unpacking" or "packing" operations.
Keywords
Full Text:
PDF (Русский)References
Задірака В., Олексюк О. Комп’ютерна арифметика багаторозрядних чисел. – К.: Наук. думка, 2003. – 263 с.
Schonhage A., Strassen V. Schnelle Multiplikation grossen Zahnel // Computing. – 1971. – 7, N 3–4. – P. 281–292.
Шенхаге А., Шрассен В. Быстрое умножение больших чисел // Кибернетика. – 1972. – Вып. 2. – С. 87–98.
Cooley J.W., Tukey J.W. An algorithm for the machine calculation of complex Fourier Series // Math Compt. – 1965. Apr. – P. 257–301.
Березовский А.И., Задирака В.К., Шевчук Л.Б. О тестировании быстродействия алгоритмов и программ выполнения основных операций для асимметричной криптографии // Кибернетика и системный анализ. – 1999. – №5. – С. 61–68.
Терещенко А.Н. Умножение больших N-разрядных чисел с вычислением только N-разрядных ДПФ // Компьютерная математика. – 2008. – № 1. – С. 122–130.
Refbacks
- There are currently no refbacks.