An Efficient Algorithm for Squaring Multi-Word Numbers
摘要
We propose a method for implementing the operation of squaring a number of N-word length (N = 2n), allowing calculations based on eight multiplications of numbers of N / 4-word length, N ≥ 4. The squaring operation is one of the basic operations of encryption, decryption, and key verification in asymmetric cryptography. The speed of asymmetric cryptography operations depends on the speed of this operation. According to the theorem, we evaluate the complexity of the proposed method for numbers of length of N words and show that the calculation can be performed based on four squarings of numbers of length of N / 4 words and four multiplications of numbers of length of N / 4 words. For squaring a four-word number, the proposed method requires eight multiplications. This is one multiplication less than in the Karatsuba method, which is used recursively. The proposed method can be used recursively, which increases the possibility of parallelizing the operation of squaring large numbers. The results of the study can be used to develop fast multi-word arithmetic algorithms and to implement the squaring of large numbers in a microchip.