一种并行动态滑动窗口算法研究与实现

Research and Application of a Parallel Dynamic Sliding Window Algorithms

摘要: 椭圆曲线倍点运算在密码学中有广泛应用，其效率直接影响密码算法与协议的性能。本文提出一种并行动态滑动窗口算法，将椭圆曲线倍点运算的标量k分为高位k₁和低位k₂，分别并行计算k₁P和k₂P后，再合并计算kP，且各自内部采用滑动窗口法。根据高位k₁和低位k₂的具体情况，设计不同的窗口大小，提升了倍点运算的速度。实验表明，该方法在保证正确性的前提下，较传统滑动窗口效率提升了约36.5%。最后，基于本文提出并行动态滑动窗口算法进一步优化了SM2公钥密码算法。

Abstract: Elliptic curve point multiplication is widely used in cryptography, and its efficiency directly impacts the performance of cryptographic algorithms and protocols. This paper proposes a parallel dynamic sliding window algorithm to accelerate point multiplication. The scalar k is split into a high-order part k₁ and a low-order part k₂, which are processed in parallel to compute k₁P and k₂P separately before merging them to obtain the final result kP. Internally, each computation employs a sliding window method to reduce the number of point additions. Additionally, different window sizes are dynamically selected based on the values of k₁ and k₂ to further optimize performance. Experimental results demonstrate that the proposed method improves computational efficiency by approximately 36.5% compared to the traditional sliding window approach while ensuring correctness. Finally, the parallel dynamic sliding window algorithm is applied to optimize the SM2 public-key cryptographic algorithm, further enhancing its performance.