UDC 519.6
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 zvk140@ukr.net
|
2 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
teramidi@ukr.net
|
OPTIMIZATION OF MULTIDIGIT MULTIPLICATION BASED ON DISCRETE TRANSFORMS
(FURIE, COSINUS, SINUS) IN PARALLEL COMPUTATIONAL MODEL
Abstract. This paper considers the multidigit multiplication operation, on whose speed the speed
of asymmetric cryptographic software and hardware depends. Algorithms for implementation
of the multiplication of two N -digit numbers based on discrete cosine and sine transforms (DCT and DST)
are proposed. Due to the use of DCT and DST, the calculations for the real and imaginary parts of the discrete
Fourier transform (DFT) of a real even-length signal are separated, which allows translating the complex number
calculations to real number calculations. Algorithm operations are replaced to preserve symmetry in real
or imaginary parts of multidigit numbers, which allows the use of DCT and DST of lower length N / 2 + 1 and increases the possibility of parallelism in the implementation of multidigit multiplication.
Keywords: multidigit multiplication, multidigit arithmetic, asymmetric cryptography, discrete cosine transform, discrete sine transform, discrete Fourier transform, fast Fourier calculation algorithm.
FULL TEXT
REFERENCES
- Anisimov A.V. Algorithmic theory of large numbers. Modular arithmetic of large numbers [in Ukrainian]. Kyiv: Academperiodica, 2001. 153 p.
- Zadiraka V., Oleksyuk O. Computer arithmetic of multi-bit numbers [in Ukrainian]. Kyiv: Nauk. Dumka, 2003. 263 с.
- Zadiraka V.K. Theory for computing the Fourier transform [in Russian]. Kyiv: Nauk. Dumka, 1983. 213 p.
- Zadiraka V.K., Tereshchenko A.M. Computer arithmetic of multi-bit numbers in serial and parallel computational models [in Ukrainian]. Kyiv: Nauk. Dumka, 2021. 136 p.
- Kachko E.G. Parallelization of multiplication algorithms for multiple precision numbers. Bulletin of the Ufa State Aviation Technical University. 2011. Е 15, N 5 (45). P. 142–147.
- Nikolaichuk Ya.M., Kasyanchuk M.M., Yakimenko I.Z., Ivasyev S.V. Effective method of modular multiplication in the number-theoretic basis of Rademacher–Chrestenson. Bulletin of the National University "Lviv Polytechnica". Computer systems and nets. 2014. N 806. P. 195–199.
- Хіміч О.М., Сидорук В.А. Використання мішаної розрядності у математичному моделюванні. Математичне та комп’ютерне моделювання. Серія: Фізико-математичні науки. 2019. Iss. 19. P. 180–187.
- Karatsuba A.A., Ofman Yu.P. Multiplication of multidigit numbers on automata. DAN USSR. 1962. Vol. 145, N 2. P. 293–294.
- Cooley J.W., Tukey J.W. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation. 1965. Vol. 19, N 90. P. 297–301.
- Schonhage A., Strassen V. Schnelle Multiplikation groen Zahlen. Computing. 1971. Vol. 7, Iss. 3–4. P. 281–292.
- Pitassi D.A. Fast convolution using the Walsh transform. Proc. 1971 Symp. Applications of Walsh Functions (13–15 April 1971, Washington, D.C., USA). Washington, D.C., 1971. P. 130–133.
- Tereshchenko A.N., Melnikova S.S., Gnativ L.A., Zadiraka V.K., Koshkina N.V. Implementation of the multiplication operation using the Walsh transform. Problemy upravleniya i informatiki. 2010. N 2. P. 102–126.
- Montgomery P.L. Modular multiplication without trial division. Mathematics of Computation. 1985. Vol. 44, N 170. Р. 519–521.
- Cook S.A. On the minimum computation time of functions. PhD thesis. Harvard University, Department of Mathematics. 1966. URL: http://cr.yp.to/bib/1966/cook.html.
- Ahmed N., Natarajan T., Rao K.R. Discrete cosine transform. IEEE Transactions on Computers. 1974. Vol. C–23, Iss. 1. P. 90–93. http://dx.doi.org/10.1109/T-C.1974.223784.
- Jain A.K. A fast Karhunen–LoЩve transform for a class of random processes. IEEE Transactions on Communications. 1976. Vol. 24, N 9. P. 1023–1029.
- Gluth R. Regular FFT–related transform kernels for DCT/DST – based polyphase filter banks. Proc. IEEE 1991 International Conference on Acoustics, Speech and Signal Processing (ICASSP 1991) (14–17 April 1991, Toronto, Canada). Toronto, 1991. P. 2205–2208.
- Chicheva M.A. Efficient even-length discrete cosine transform algorithm. computer optics. 1998. N 18. P. 147–149.
- Hnativ L.O., Luts V.K. Integer modified sine – cosine transformations of type VII. Construction method and separate directional adaptive transformations for intra-prediction with 8x8 brightness blocks in image / video encoding. Kibernetyka ta systemnyi analiz. 2021. Vol. 57, № 1. P. 178–190.
- Tereshchenko A.M. Optimization of multi-bit multiplication based on FFT in a parallel computational model. Zakhyst informatsiyi. 2014. Vol. 16, N 3. P.178–184.
- Tereshchenko A.M., Zadiraka V.K. Implementation of multi-bit multiplication operation based on discrete cosine and sine transforms. Kibernetyka ta komp'yuterni tekhnolohiyi. 2021. N 4. P. 61–79.
