Performing block form reductions modulo non-Mersenne primes in cryptographic protocols

摘要

In a general aspect, a cryptography process performs modular operations, where the modulus is a non-Mersenne prime. In some aspects, an integer is obtained during execution of a cryptography protocol defined by a cryptosystem. A prime modulus is defined by the cryptosystem in terms of a set of constants. The set of constants includes at least a first constant and a second, distinct constant. A set of block coefficients is computed to represent the integer in a block form. The plurality of block coefficients includes a first block coefficient obtained by a first modular reduction modulo the first constant, and a second block coefficient obtained by a second modular reduction modulo the second constant. A reduced representation of the integer is computed based on the plurality of block coefficients, such that the reduced representation is less than the prime modulus.