AN EFFICIENT ALGORITHM FOR SQUARING MULTI-WORD NUMBERS

A method of implementing the operation of squaring a number with a length of N words (N = 2n ) is proposed, which allows performing calculations based on eight multiplications of numbers with a length of N / 4 words (N ≥ 4 ). The squaring operation is one of the main operations of encryption, decryption, and verification of keys in asymmetric cryptography. The speed of operations of asymmetric cryptography depends on the speed of the square operation. The complexity of the proposed method for numbers with a length of N words is evaluated in the form of the theorem, and it is shown that the calculation can be performed based on four squares of numbers with a length of N / 4 words and four multiplications of numbers with a length of N / 4 words. For squaring a 4-word number, the developed method requires eight one-word multiplication operations, one multiplication less than in the Karatsuba‘s method, which is used recursively. The method can be used recursively, which increases the possibility of parallelizing the implementation of squaring large numbers. The results of the paper can be used for the development of fast multi-word arithmetic algorithms and the implementation of the squaring of large numbers in a circuit design. Keywords: multiword arithmetic, multiword multiplication, multiword squaring, multiword squaring by modulo, asymmetric cryptography.