返回Google圖書搜尋

A Modular Multiplication Algorithm with Triangle Additions

Kyōto Daigaku. Joho Kogaku KyoshitsuN. Takagi

出版	Department of Information Science, Faculty of Engineering, Kyoto University, 1992
URL	http://books.google.com.hk/books?id=48RPHAAACAAJ&hl=&source=gbs_api

註釋Abstract: "A new algorithm for modular multiplication with a large modulus is proposed. In the algorithm, we first add up the upper half triangle of the whole partial products, and then calculate the residue of the sum. Next, we add the sum of the lower half triangle of the whole partial products to the residue, and then calculate the residue of the total amount. We use a new efficient procedure for residue calculation. For an n-word modular multiplication, the algorithm requires only (n+1)- word memory space for storing the intermediate result and requires about the same number of operations as for an n-word multiplication and a 2n-word by n-word division. The algorithm is fast and efficient for implementation on a small computer with small amount of main memory such as a card computer."