Quisquater Reduction
AssigneeKoninklijke Philips Electronics N.V.
InventorGerardus Hubert
Life of this patent
Estimating the term…
Abstract
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’.
Claims15
A method 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 X has a length (m+n) bits, comprising the steps of:
- a) initialising a product register, P
- b) loading a first one of the j words of Y into a multiplier;
- c) multiplying the loaded word of Y by X to form an intermediate product T;
- d) updating the product register P with the sum of T and P*2p;
- e) reducing the contents of the product register P by subtraction of a value PH (N′/2);
- f) loading a successive one of the j words of Y into the multiplier and repeating steps c) to e) for each one of the j words of Y,
- wherein 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’, and
- wherein PH is selected as the (p+2) most significant bits of P in the register.
A processor 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 X has a length (m+n) bits, comprising:
- a) initialisation means for initialising a product register, P
- b) loading means for loading a first one of the j words of Y into a multiplier;
- c) a multiplier for multiplying the loaded word of Y by X to form an intermediate product T;
- d) update means for updating the product register P with the sum of T and P*2p;
- e) reduction means for reducing the contents of the product register P by subtraction of a value PH (N′/2);
- f) control means for loading successive ones of the j words of Y into the multiplier and repeating the functions of the multiplier, the update means and the reduction means for each one of the j words of Y,
- wherein 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’, and
- wherein PH is selected as the (p+2) most significant bits of P in the register.
Dependencies are inferred from the claim text.