QUISQUATER REDUCTION,申请号WO2003IB03949-传众专利搜索

QUISQUATER REDUCTION

申请公布号：WO2004027597(A3)

申请号：WO2003IB03949

申请日期：2003.09.10

申请公布日期：2004.11.11

申请人：

KONINKLIJKE PHILIPS ELECTRONICS N.V.;HUBERT, GERARDUS, T., M.

发明人：HUBERT, GERARDUS, T., M.

分类号：G06F7/72

主分类号：G06F7/72

摘要：A method and apparatus for calculating the product P of a first number X and a second number Y, modulo N, where Y is partitioned into j words each of length p bits, and has a length (m + n) bits, cyclically operates on successive ones of the j words of Y, carrying out intermediate modulo reductions of the intermediate products formed. A specially selected multiple, N', of N is used so that only a single reduction of the intermediate based on N' guarantees that the intermediate product P is never longer than (m+n) bits at the end of each cycle. N' is an integer multiple of N, and the value N' is selected such that the (m - 1) most significant bits are equal to '1', and the least significant bit is '0'.