摘要
针对模乘运算的模超过一半整数位会发生算术溢出,不使用高精度运算就无法处理的问题,提出一种利用同余关系缩小乘积的模乘算法。通过将整数分解成两位数,按照两位数乘法的原理,将高位部分乘积用同余关系缩小,避免了乘法运算过程的算术溢出。结果表明,该方法可以将64位整数为基础的模乘运算的模扩大到62位。
The modular multiplication with the modulus greater than the value of half bits of the integer would result in overflow, and the high precision arithmetic operations have to be used, To avoid the use of high precision arithmetic operations, a modular multiplication algorithm including reduction by congruence was proposed. By decomposing the operands to double-digit numbers and reducing the product of higher digit by congruence, operation overflow was avoided. The experimental results show that the modular multiplication based on 64 digit integers can use the modulus of up to 62 digit.
出处
《计算机应用》
CSCD
北大核心
2012年第9期2470-2471,2495,共3页
journal of Computer Applications
关键词
整数
模乘
同余
溢出
integer
modular multiplication
congruence
overflow
