Review of Modular Multiplication Algorithms over Prime Fields for Public-Key Cryptosystems

Modular multiplication is a pivotal operation in public-key cryptosystems such as RSA, ElGamal, and ECC. Modular multiplication design is crucial for improving overall system performance due to the large-bit-width operation with high computational complexity. This paper provides a classification of integer multiplication algorithms based on their implementation principles. Furthermore, the core concepts, implementation challenges, and research advancements of multiplication algorithms are systematically summarized. This paper also gives a brief overview of modular reduction algorithms for various types of moduli and discusses the implementation principles, application scenarios, and current research results. Finally, the detailed research development of modular multiplication algorithms in four major classes over prime fields is deeply analyzed and summarized, making it essential as a guide for future research.