18501256. APPARATUS AND METHODS FOR PRIME FIELD MODULAR REDUCTION (Microsoft Technology Licensing, LLC)

APPARATUS AND METHODS FOR PRIME FIELD MODULAR REDUCTION

Organization Name

Microsoft Technology Licensing, LLC

Inventor(s)

Jay Scott Fuller of Scotts Valley CA US

APPARATUS AND METHODS FOR PRIME FIELD MODULAR REDUCTION

This abstract first appeared for US patent application 18501256 titled 'APPARATUS AND METHODS FOR PRIME FIELD MODULAR REDUCTION

Original Abstract Submitted

Apparatus and methods for prime field modular reduction are described. As an example, a custom modular reduction digital circuit for reducing an n-bit integer based on a modulus, where the modulus comprises a k-bit integer for use with a cryptographic algorithm, is described. The custom modular reduction digital circuit includes a first circuit to generate at least two partial results by processing: (1) k lower order significant bits of the n-bit integer and (2) at least a subset of bits for congruent representations corresponding to any n-k higher order bits of the n-bit integer that are higher in significance than the most significant bit of the k-bit integer. The custom modular reduction digital circuit further includes a second circuit to process the at least two partial results, output by the first circuit, to generate a reduced version of the n-bit integer for use with the cryptographic algorithm.