Fully homomorphic encryption (FHE) and zero-knowledge proof (ZKP) are emerging as promising solutions for data security in today’s data-driven world. However, the widespread adoption of these encryption techniques is hindered by their significant computational overhead, primarily resulting from core cryptographic operations that involve large integer arithmetic. To manage this complexity, this paper presents a formalization of multi-word modular arithmetic (MoMA), which breaks down arbitrary bit-width integer arithmetic into operations based on machine words. We further develop a rewrite system that implements MoMA, designed to be compatible with any compiler or code generator by recursively rewriting on data types. We evaluate MoMA by generating cryptographic kernels, including basic linear algebra subprogram (BLAS) operations and the number theoretic transform (NTT), across various GPUs. Our MoMA-based BLAS operations outperform state-of-the-art multi-precision libraries by orders of magnitude, and MoMA-based NTT achieves near-ASIC performance on commodity GPUs.