Optimized multi-precision division
In an embodiment, multi-precision numbers A and B are accessed from a storage device (e.g., a memory array), where A is a dividend and B is a divisor. A multi-precision division operation is iteratively performed on the numbers A and B including: performing a multi-precision subtraction operation on A and B during a first iteration of the multi-precision division operation; performing a multi-precision addition operation on A and B during a second iteration of the multi-precision division operation as a result of a determination that a final borrow occurred during the subtraction operation; and performing a multi-precision addition operation on A and B after a final iteration of the multi-precision division operation.
1. An apparatus comprising:
an instruction register configured to store an instruction for a multi-precision division operation;
an arithmetic logic unit (ALU);
a control unit configured to command or instruct the ALU to perform one or more multi-precision division operations comprising:
accessing from a memory array multi-precision numbers A and B, where A is a dividend and B is a divisor;
iteratively performing, by the ALU according to the instruction, the multi-precision division operation on the numbers A and B including:
performing a multi-precision subtraction operation on A and B during a first iteration of the multi-precision division operation, the multi-precision subtraction operation being performed a word at a time, including propagating a borrow word by word;
performing a multi-precision addition operation on A and B during a second iteration of the multi-precision division operation as a result of a determination that a final borrow occurred during the subtraction operation, the multi-precision addition operation being performed a word at a time, including propagating a carry word by word; and
performing a multi-precision addition operation on A and B after a final iteration of the multi-precision division operation.
2. The apparatus of claim 1 , where the multi-precision division operation is a step in a modular reduction operation used in a cryptographic operation.
3. The apparatus of claim 1 , where A and B each span multiple machine words in the memory array or a hardware register.
4. The apparatus of claim 3 , where the multi-precision division is a binary division that is implemented using bit shifting operations.
5. The apparatus of claim 4 , further comprising:
determining a number of bit positions that B can be shifted without overflowing the memory array; and
determining the number of iterations of the multi-precision division operation based on the determined number of bit positions.
6. The apparatus of claim 1 , where the apparatus is a smart card.
7. The apparatus of claim 1 , where the apparatus is a secure processor.