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
2015-02-03
Issue
Section
Articles
License
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
