Square a Multi-Digit Number on 8 Processors in a Parallel Computational Model
Introduction. Currently, data security and confidentiality are becoming an urgent challenge not only for individuals, but also at the state level. The level of cyberattacks has grown to such an extent that hackers can disable servers, change data in cloud storage, which makes it impossible to work e...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
V.M. Glushkov Institute of Cybernetics
2025-03-01
|
| Series: | Кібернетика та комп'ютерні технології |
| Subjects: | |
| Online Access: | http://cctech.org.ua/13-vertikalnoe-menyu-en/690-abstract-25-1-4-arte |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Introduction. Currently, data security and confidentiality are becoming an urgent challenge not only for individuals, but also at the state level. The level of cyberattacks has grown to such an extent that hackers can disable servers, change data in cloud storage, which makes it impossible to work entire government agencies for a long period, which requires significant efforts to restore resources. Cyberattacks are becoming more organized and selective. The use of asymmetric cryptographic software and hardware complexes is becoming an obligatory element of protection. The speed of asymmetric cryptographic operations such as encryption, decryption, key verification depends on the speed of the modulo squaring operation. Using fast methods, the operation of squaring a number of N digits can be performed with less complexity than the operation of multiplying two numbers of N digits.
This paper considers a method for implementing the squaring operation, which allows reducing the number of multiplication and squaring operations compared to the Karatsuba method. The proposed method can be used recursively and is convenient for parallelization, which increases its range of effective use.
The purpose of the article is to reduce the number of single-digit multiplication and squaring operations to speed up the execution time of the operation of squaring a number with a length of N digits (N=2n, N?4). Reduce the number of multiplications with a length of N/4 digits to 8 operations in the case of squaring a number with a length of N digits. Reduce the overall computational complexity and find a modification in which the number of addition and subtraction steps will be the smallest compared to other modifications. Build a squaring algorithm based on the modification found. Find an efficient method of squaring numbers with a length of up to 4096 bits with the possibility of parallelization.
Results. The structure of a number that is divided into four parts for the implementation of the squaring operation is considered. The effect of splitting a 4-digit number into a 2-digit number and a 4-digit number with a simpler structure, artificially created due to the repetition of its parts, on the implementation of the squaring operation is investigated. A method for implementing the squaring operation of a 4-digit number in eight one-digit multiplications is developed, which is one multiplication less than in the Karatsuba method, which is performed recursively. To obtain the result of the squaring operation, linear combinations of the multiplication results are used. The paper presents such a modification of the implementation, which has a small number of addition and subtraction operations in linear combinations. An algorithm based on the proposed modification is presented, which shows how a 4-digit number with a heterogeneous structure can be split into a 2-digit number and a 4-digit number with a simpler structure due to repetition. An analysis of the complexity in terms of the number of single-digit multiplication operations depending on the length of the number N is carried out in the case of recursive use of the algorithm for implementing the square operation for comparison with the Karatsuba method.
Conclusions. The paper presents an algorithm for implementing the operation of squaring a 4-digit number based on eight single-digit multiplications, three of which are squaring operations. The example shows the implementation of the operation of squaring a 4-digit number with a heterogeneous structure. The complexity of the proposed method is estimated for numbers of length N digits, and it is shown that the calculation can be performed on the basis of three squaring operations of numbers of length N/4 digits and five multiplications of numbers of length N/4 digits. Based on the comparative analysis, it is shown that the proposed squaring method is better than the Karatsuba method by 11 % for (N = 4) and by 16 % with increasing N. To verify the result of the calculation, the algorithm-program SquaringNumber2aa in the APL programming language is implemented. The method can be used recursively, which increases the possibilities of parallelizing the implementation of the square operation of large numbers, which increases its effective range of use to 4096 bits. |
|---|---|
| ISSN: | 2707-4501 2707-451X |