Patent ID: 6917957
Filing Date: 2005-07-12
Classification: G06F

Abstract:
1. An apparatus that performs modular division, comprising: a register A that is initialized with a value X; a register U that is initialized with a value Y; a register B that is initialized with a value M; a register V that is initialized with a value 0; a counter CA that indicates an upper bound for the most-significant non-zero bit of register A; a counter CB that indicates an upper bound for the most-significant non-zero bit of register B; and an updating mechanism that is configured to iteratively reduce the contents of registers A and B to a value of one by applying a plurality of invariant operations to registers A, B, U and V; wherein updating mechanism is configured to use the counters CA and CB to estimate the relative magnitudes of the values stored in registers A and B instead of performing an expensive comparison operation between register A and register B.