M-ary Precomputation-Based Accelerated Scalar Multiplication Algorithms for Enhanced Elliptic Curve Cryptography

Efficient scalar multiplication is critical for enhancing the performance of elliptic curve cryptography (ECC), especially in applications requiring large-scale or real-time cryptographic operations. This paper proposes an M-ary precomputation-based scalar multiplication algorithm, aiming to optimize both computational efficiency and memory usage. The method reduces the time complexity from $\mathrm{\Theta }(Q\log p)$ to $\mathrm{\Theta }\left(\frac{Q\log p}{\log Q}\right)$ and achieves a memory complexity of $\mathrm{\Theta }\left(\frac{Q\log p}{{\log }^{2}Q}\right)$. Experiments on ElGamal encryption and NS3-based communication simulations validate its effectiveness. On secp256k1, the proposed method achieves up to a 59% reduction in encryption time and 30% memory savings. In network simulations, the binary-optimized variant reduces communication time by 22.1% on secp384r1 and simulation time by 25.4% on secp521r1. The results demonstrate the scalability, efficiency, and practical applicability of the proposed algorithm. The source code will be publicly released upon acceptance.