Efficient Modular Arithmetic using Vectorization on CPUs and GPUs
summary
Claims a simplified RNS Montgomery method that eliminates unnecessary elementwise modular multiplies and turns a single large-field modular multiply into a highly vectorizable operation on CPUs (AVX512) and GPUs. Implements CPU and GPU code, shows ~4x speedup ceiling on AVX512 and a measured 2x (should approach 4x) win on a 6,144-bit modular exponentiation test limited by GPU thread count, at the cost of extra precomputed storage; conjectures custom t^2 multiplier hardware could yield near t log t critical-path exponentiation and order-of-magnitude public-key speedups.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 0:47Modular arithmetic in cryptography
- 3:02Constant-time requirements
- 5:59Montgomery and Barrett overview
- 7:43Parallelism vs vectorization
- 9:11Residue Number Systems in crypto
- 12:51CRNS base conversion core
- 17:3330 years of CRNS evolution
- 19:45Complexity metrics and optimizations
- 21:36GPU RNS Montgomery
- 24:50GPU performance results
- 26:15AVX CPU vectorization benchmarks
- 28:00MKHSS modular exponentiation speedup
- 29:48Custom hardware for modular arithmetic
- 31:14Closing thoughts
- 32:17Q&A
related talks
14mUsing Proposed Vector And Crypto Extensions For Fast And Secure Boot
24mbig number small computer
40mImplementation
14mSecurity Task Group Update And RISC V security Extension
58mFast Cryptographic Code via Partial Evaluation
16mRISC-V Instruction Set Extensions for Cryptography - From Research to Standardization
19mOn the Efficiency of RISC-V Cryptographic Instruction Set Extensions
31m“Multi-Precision Arithmetic for Cryptology in C++, at Run-Time and at Compile-Time”