Modular Reduction for Cryptographic Operations

A device for performing a modular reduction of an input number C modulo of a modulus N, wherein the device comprises a processing unit, the processing unit comprising processing circuitry and memory, the processing unit being configured to:

• calculate an intermediate value q, from which a quotient of the input number C divided by the modulus N is approximated,
• extract a number Q for a reduction operation C−Q·N from the intermediate value q,
• extract information from the intermediate value q, wherein on the basis of the information prior to performing the reduction operation C−Q·N it is possible to determine whether a final reduction is to be performed,
• perform the reduction operation C−Q·N,
• depending on the information, perform the final reduction or not perform the final reduction.