计算机应用 ›› 2012, Vol. 32 ›› Issue (09): 2470-2471.DOI: 10.3724/SP.J.1087.2012.02470

• 先进计算 • 上一篇    下一篇

扩展到整数类型范围的模的模乘算法

邵荣*   

  1. 南京大学 数学系,南京 210093
  • 收稿日期:2012-03-26 修回日期:2012-05-05 发布日期:2012-09-01 出版日期:2012-09-01
  • 通讯作者: 邵荣
  • 作者简介:邵荣(1965-),男,安徽绩溪人,副教授,博士,主要研究方向:计算数论。

Modular multiplication algorithm with modulus expanded to maximum of integer

SHAO Rong*   

  1. Department of Mathematics,Nanjing University,Nanjing Jiangsu 210093,China
  • Received:2012-03-26 Revised:2012-05-05 Online:2012-09-01 Published:2012-09-01
  • Contact: Rong Shao

PDF

摘要： 针对模乘运算的模超过一半整数位会发生算术溢出,不使用高精度运算就无法处理的问题,提出一种利用同余关系缩小乘积的模乘算法。通过将整数分解成两位数,按照两位数乘法的原理,将高位部分乘积用同余关系缩小,避免了乘法运算过程的算术溢出。结果表明,该方法可以将64位整数为基础的模乘运算的模扩大到62位。

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

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

中图分类号: 

版权所有 © 2021 四川计算机应用杂志社有限公司
蜀ICP备 05010208 号-3　新出网证(川)字026号
技术支持：北京玛格泰克科技发展有限公司
访问总数：
今日访问：