Modular exponentiation via the explicit Chinese remainder theorem
Daniel J. Bernstein, Jonathan Sorenson · Mathematics of Computation · 2006
Fix pairwise coprime positive integers p 1 , p 2 , … , p s p_1,p_2,\dots ,p_s . We propose representing integers u u modulo m m , where m m is any positive integer up to roughly p 1 p 2 ⋯ p s \sqrt {p_1p_2\cdots p_s} , as vectors ( u mod p 1 , u mod p 2 , … , u mod p s ) (u\bmod p_1,u\bmod p_2,\dots ,u\bmod p_s) . We use this representation to obtain a new result on the parallel complexity of modular exponentiation: there is an algorithm for the Common CRCW PRAM that, given positive integers x x , e e , and m m in binary, of total bit length n n , computes x e mod m x^e\bmod m in time O ( n / lg