Modular reduction operation methods and apparatuses

A computing device, comprising a memory and a processor, wherein the memory stores executable code, and when the processor executes the executable code, the computing device is caused to:

• obtain a modular reduction factor r1 corresponding to the first modulus;
• detect at least one group of significant bits in the modular reduction factor r1, wherein the significant bits are a plurality of consecutive bits that comprise non-overlapping bits, and the non-overlapping bits are adjacent different bits;
• compute a first product of each group of significant bits and the given value x;
• and
• sequentially merge the first product with second products, and shift a merging result to the right by a first quantity of bits to obtain a first reference factor, wherein a single second product is determined by performing a corresponding bit operation on the given value x based on a corresponding single group of redundant bits, and the single group of redundant bits comprise a plurality of consecutive overlapping bits;
• subtract a third product of the first reference factor and the first modulus from the given value x, to obtain a second reference factor;
• and
• compare the second reference factor with the first modulus to determine a modular reduction result of the given value x for the first modulus based on a comparison result.

A non-transitory computer-readable storage medium storing instructions, wherein the non-transitory computer-readable storage medium stores a computer program, which when executed by a processor causes the processor to:

• obtain a modular reduction factor r1 corresponding to the first modulus;
• detect at least one group of significant bits in the modular reduction factor r1, wherein the significant bits are a plurality of consecutive bits that comprise non-overlapping bits, and the non-overlapping bits are adjacent different bits;
• compute a first product of each group of significant bits and the given value x;
• and
• sequentially merge the first product with second products, and shift a merging result to the right by a first quantity of bits to obtain a first reference factor, wherein a single second product is determined by performing a corresponding bit operation on the given value x based on a corresponding single group of redundant bits, and the single group of redundant bits comprise a plurality of consecutive overlapping bits;
• subtract a third product of the first reference factor and the first modulus from the given value x, to obtain a second reference factor;
• and
• compare the second reference factor with the first modulus to determine a modular reduction result of the given value x for the first modulus based on a comparison result.