Efficient Modular Arithmetic using Vectorization on CPUs and GPUs

Learn how to accelerate modular arithmetic operations using vectorization techniques on both CPUs and GPUs in this 33-minute conference talk from the Simons Institute. Explore the computational challenges of modular multiplication in large prime fields, which forms the backbone of cryptographic and scientific algorithms and often dictates overall algorithm runtime. Discover a new RNS Montgomery multiplication method that simplifies existing approaches and eliminates unnecessary elementwise modular multiplications through vectorization. Understand how this breakthrough enables significant latency reduction for single modular multiplications under generic primes, moving beyond the traditional approach of only accelerating batches of independent operations. Examine the implications for number-theoretic cryptography, where virtually all operations can benefit from vectorization speedups. Gain insights into the technical details of this simplified RNS structure and its potential to transform computational efficiency across cryptographic applications.