Back to results
US 2006/0198516 A1Published application
Systems and methods for generating random addition chains
AssigneeMicrosoft Corporation
InventorsAnton Mityagin, Ilya Mironov, Yaacov Nissim Kobliner
Life of this patent
Estimating the term…
Abstract
An addition chain is first generated, and then an integer x is derived from it. Doubling and star steps may be implemented in the addition chain. This approach eliminates the computationally expensive step of generating the addition chain from an exponent, and therefore can greatly reduce the computation time of the modular exponentiation.
Claims20
A method of exponentiation comprising:
- generating an addition chain;
- and
- determining an exponent based on the addition chain.
A method of generating an addition chain comprising:
- (a) initializing a chain;
- (b) flipping a biased coin;
- (c) performing a doubling step or a star step on the chain based on the biased coin flip;
- (d) if a star step is performed, then choosing a random element and adding the random element to a set of random elements;
- and
- (e) determining whether the size of the set of random elements is outside a bounded interval.
3 more elements
A computer readable medium having computer executable instructions stored thereon for performing a method comprising:
- generating an addition chain;
- and
- determining an exponent based on the addition chain.
Dependencies are inferred from the claim text.