A Multiword Multiplication Algorithm Based on the Mersenne Transform

Mathematical Methods of Operations Research · Springer Nature · 2026-09-01 · DOI: 10.1007/s10559-026-00908-w

Аннотация

The paper presents an algorithm for implementing multiword multiplication based on the number-theoretic Mersenne transform. Mersenne numbers and their properties are widely used in cybersecurity and digital signal processing. Algorithms based on the Mersenne transform can also be implemented on quantum computers with the possibility of superparallelization. Multiword multiplication is a fundamental operation in encryption, decryption, and the generation and verification of keys in asymmetric cryptography. The performance of asymmetric cryptographic operations depends on the speed of this multiword operation. A new fast algorithm is presented for finding the inverse number used to compute the inverse Mersenne transform, which makes it possible to construct algorithms for performing operations on numbers with lengths of one million bits or more. A complexity estimate is obtained for the algorithm based on the Mersenne transform for numbers of length N words, and it is noted that such an algorithm can be executed recursively. The upper bound on the maximum possible value of the multiplier as a function of the length of the Mersenne transform p for the multiword multiplication algorithm is analyzed. A new algorithm for Mersenne modular multiplication is proposed, based on two half-length multiplication operations instead of three multiplications using the Karatsuba method. A comparative analysis of the computational complexity, in terms of the number of single-word multiplication operations, of algorithms based on the Mersenne transform combined with the Karatsuba method and on the Karatsuba method alone is performed using the example of a multiword squaring operation.

Читать у издателя →

Похожие статьи