Optimization of multi-digit Multiplication based on FFT in Parallel computational model
DOI:
https://doi.org/10.18372/2410-7840.16.7533Keywords:
parallel computational model, asymmetric cryptography, multidigit arithmetic, multidigit multiplication, DFT, FFTAbstract
It is considered the operation of multi-digit multiplicationfor parallel computational model, that has biggest influenceon performance of asymmetric cryptographic computer systems. It is given modification of N-digit multiplicationalgorithm based on FFT and DTF`s coefficientspreviously computed. New algorithm operates with multidigitsof the length of N, contrary to standard algorithmthat uses multi-digits of the length of 2N. Algorithm reducesin two times the number of used parallel processorskeeping the same computational complexity of each processorin comparison with standard algorithm. Givenalgorithm is also efficient in sequential computationalmodel.References
. Zadiraka V.K. (1985) «About requirements for
parallel data processing in FFT processor» Algorithm
and computer software optimization, Kyiv.: V.M.
Glushkov Institute of Cybernetics of NAS of
Ukraine, P. 3-10.
. Zadiraka V., Oleksyuk O. (2003) «Computer
multidigit arithmetic: Naukove vidanya», Kyiv, 263 p.
. Tereshchenko A.N. (2008) «Multiplication of big
numbers of the length of N with computing only
DTF of the length of N», Computer mathematics,
№ 1, P. 122-130.
. Tereshchenko A.N., Zadiraka V.K. (2012)
«Optimization of big numbers of the length of N
multiplication based on DTF of the length of N»,
Programming problems, № 4, P. 116-130.
Downloads
Published
How to Cite
Issue
Section
License
The scientific journal adheres to the principles of Open Access and provides free, immediate, and permanent access to all published materials without financial, technical, or legal barriers for readers.
All articles are published in Open Access under the Creative Commons Attribution 4.0 International (CC BY 4.0) license.
Copyright
Authors who publish their works in the journal:
-
retain the copyright to their publications;
-
grant the journal the right of first publication of the article;
-
agree to the distribution of their materials under the CC BY 4.0 license;
-
have the right to reuse, archive, and distribute their works (including in institutional and subject repositories), provided that proper reference is made to the original publication in the journal.
