Multidigit Modular Multiplication With The Explicit Chinese Remainder Theorem
Multidigit Modular Multiplication With The Explicit Chinese Remainder Theorem
复制标题
具有显式中国剩余定理的多位数模乘法
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
D. Bernstein
中科院分区：
文献类型：
--
作者：
D. Bernstein
确定互质模m1，. . . ms，每个都有几个数字。设n是一个几百位的整数。我们展示了如何算术模n可以执行整数u表示为向量（u模m1，. . .，u mod ms）。这种方法不涉及多精度算法，除了在一个简单的预计算;它是实用的软件和非常适合硬件。我们的主要工具是显式中国剩余定理，它确切地说明了u与u mod mi的特定线性组合的不同之处。
Fix coprime moduli m1, . . . ,ms, of a few digits each. Let n be an integer of a few hundred digits. We show how arithmetic modulo n may be performed upon integers u represented as vectors (u mod m1, . . . , u mod ms). This method involves no multiprecision arithmetic, except in an easy precomputation; it is practical in software and extremely well suited for hardware. Our main tool is the Explicit Chinese Remainder Theorem, which says exactly how u differs from a particular linear combination of the remainders u mod mi.