Patent ID: 7961877

Claim:
A method for modular exponentiation, comprising: dividing, via circuitry, a first polynomial into a plurality of segments; generating, via the circuitry, a first product by multiplying the plurality of segments of the first polynomial with a second polynomial; generating, via the circuitry, a second product by shifting the contents of an accumulator with a factorization base having a bit length of D, wherein D is selected to be approximately equal to the bit length of a segment of the first polynomial so that the second product is limited to the bit length of the contents of the accumulator plus D; adding, via the circuitry, the first product and the second product to yield a first intermediate result; reducing, via the circuitry, the first intermediate result to yield a second intermediate result; and generating, via the circuitry, a public key based on, at least in part, the second intermediate result.