关键词: 整数, 模乘, 同余, 溢出

Abstract: 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.

Key words: integer, modular multiplication, congruence, overflow