Emod a fast modulus calculation for computer systems
AssigneeIntel Corporation
InventorErik Højsted
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.
Claims28
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 and in response to a key negotiation request in a computing device, determining, by said computing device, 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,
- upon conclusion of a final iteration, determining, by said computing device, a modulus of a result thereof using a true modulus n;
- and
- storing the modulus of a result thereof using a true modulus n memory.
A method of resolving an (A·B) mod n operation, comprising,
- iteratively, for each of several words of B and in response to a key negotiation request in a computing device:
- shifting, by a computing device, a value c by a word length,
- adding, by computing device, to the shifted value c, a value A·B[i], where B[i] is the ith word of B,
- performing, by said computing device, an emod operation of a result of the addition, using a phantom modulus mn that is a multiple of n,
- following a last iteration, performing, by said computing device, a modulus operation on the result of the addition from the last iteration;
- and
- storing the result of the modulus operation in memory.
A method for resolving an (A·B) mod n, operation comprising:
- iteratively, for each of several words of B and in response to a key negotiation request in a computing device:
- generating, by said computing device, a quotient q from a higher order portion of an earlier valuation of c,
- generating, by said computing device, a remainder r from a lower order portion of the value c,
- revaluing, by said computing device, 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, by said computing device, a modulus operation on the result of the revaluing from the last iteration;
- and
- storing the result of the modulus operation in memory.
A method of resolving an (A·B) mod n operation, comprising:
- Iteratively, for each of several words of B and in response to a key negotiation request in a computing device:
- Generating, by said computing device, a quotient q[i] from a higher order portion of an earlier valuation of c, where i represents the current iteration,
- Generating, by said computing device, a remainder r[i] from a lower order portion of the value c,
- Shifting, by said computing device, left quotient q[i−1] by word width,
- Revaluing, by said computing device, c to be A·9 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, by said computing device, a modulus operation on the result of the revaluing from the last iteration;
- and
- storing the result of the modulus operation in memory.
A method of resolving an A8 mod n operation, comprising:
- iteratively, for each bit position i of B and in response to a key negotiation request in a computing device:
- Performing, by said computing said computing device, a c=(c·c) emod n operation, and
- if the ith bit position of B is a 1, performing, by said computing device, a c=(c·A) emod n operation;
- and
- following a last iteration, performing, by said computing device, 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, wherein mn is an integer multiple of n;
- and
- storing the modulus result in memory.
Dependencies are inferred from the claim text.