Emod a fast modulus calculation for computer systems
AssigneeIntel Corporation
InventorErik Hojsted
Life of this patent
Estimating the term…
Abstract
An emod operation is a computational substitute for a traditional modulus operation, one that is computationally less expensive but also less precise. Where a modulus operation may be defined for some base number n, the emod operation determines a modulus of an operand using a “phantom modulus,” one that is an integer multiple of n. The phantom modulus is chosen to make emod calculations computationally inexpensive when compared to a modulus operation. Thus, the emod operation is particularly useful for multiplications or exponential operations using very large operands. Upon conclusion of interstitial processing associated with the multiplications or exponential operations, a single, traditional modulus operation may be used to obtain a final result.
Claims5
A method of performing a modulus operation upon an operand that is represented by mathematical function to be performed iteratively, the modulus taken with respect to a value n, comprising:
- upon conclusion of each of a plurality of interstitial iterations, determining a modulus of a result thereof using a phantom modulus that is a multiple of n, the phantom modulus approximating 2k for some arbitrary k, and
- upon conclusion of a final iteration, determining a modulus of a result thereof using a true modulus n.
A method of resolving an (A·B) mod n operation, comprising,
- iteratively, for each of several words of B:
- shifting a value c by a word length,
- adding to the shifted value c, a value A·B[i], where B[i] is the ith word of B, performing an emod operation on a result of the addition, using a phantom modulus mn that is a multiple of n, and
- following a last iteration, performing a modulus operation on the result of the addition from the last iteration.
A method of resolving an (A·B) mod n, operation comprising:
- iteratively, for each of several words of B:
- generating a quotient q from a higher order portion of an earlier valuation of c,
- generating a remainder r from a lower order portion of the value c,
- revaluing c to be A·B[i]+r+d·q, where d is a precision value of a phantom modulus, where B[i] is the ith word of B,
- following a last iteration, performing a modulus operation on the result of the revaluing from the last iteration.
A method of resolving an (A·B) mod n operation, comprising:
- iteratively, for each of several words of B:
- generating a quotient q[i] from a higher order portion of an earlier valuation of c, where i represents the current iteration,
- generating a remainder r[i] from a lower order portion of the value c,
- shifting left a quotient q[i−1] by a word width
- revaluing c to be A·B[i]+r[i]+d·q[i−1], where d is a precision value of a phantom modulus, where B[i] is the ith word of B and the revaluing uses the shifted quotient,
- following a last iteration, performing a modulus operation on the result of the revaluing from the last iteration.
A method of resolving an AB mod n operation, comprising:
- iteratively, for each bit position i of B:
- performing a c=(c·c) emod n operation, and
- if the ith bit position of B is a 1, performing a c=(c·A) emod n operation;
- and
- following a last iteration, performing A mod N operation of c obtained from the last operation,
- wherein the emod n operation calculates a modulus result from a phantom modulus mn, where mn is an integer multiple of n.
Dependencies are inferred from the claim text.