| Abstract |
Given work develops approach Shtrassen [1] to quick multiplying multidigit number in a part of the use for its realization of the original modification algorithm of the quick transformation Fourier (QTF) [2], the mark to difficulties, comparative analysis with other known methods, recommendation on regions its effective use and program and device realization.
For program realization on computer asymmetric cryptographic algorithm necessary to have a library effective on speed algorithm and programs of the execution operation with multidigit number.
Time to operations of the multiplying on processor with fixed by length of the word proportional square of the length operand . But if specially to this effect construct consecutively-parallel hardware provision, that this time can be reduced before . In this case required amount logical element will proportional be a length operand . Time of the work the most high-speed realization proportional, but they require the order logical element.
However, have at present found broad using methods, allowing calculate required product quicker, than for step. This for method Karacuby, which difficulty is , where [3]. The method polynomial since running time of the order . The Algorithm Tooma-Kuka with difficulty of the order [4]. The Algorithm Shenhage - Shtrassena allows to multiply two - a class numbers, executing for step (the bit operation) [1].
All are these methods are founded on information of the multiplying - a class numbers to multiplying numbers with smaller number category.
|
