43.3.5 Modular Arithmetic Services

This section provides a complete description of the modular arithmetic services, which consists of two sets:

  • Modular reductions, which can be used as stand alone operations, or used as a final step of most arithmetic operations (full and small multiplications, squaring).
  • Modular operations, which include modular exponentiations (with or without using the CRT) and a probabilistic prime number generation.

These operations work on general data so the modulus has no special form. The modular services are available through:

  • a Fast form (may return a congruence of the result, with a high probability to have a Normalized result)
  • a Normalized form (returns the exact result, strictly lower than the modulus)
  • a Euclidean form (returns the exact result, strictly lower than the modulus)
The following table describes the modes of the modular reduction with the hypothesis:
  • In GF(p): The modulus is N with length NLength in bytes
  • In GF(2n): The modulus is P[X] with length NLength in bytes

For the exact calculus of NLength see below.

Table 43-43. Modular Reduction Modes
Modular Reduction FormInput DynamicResult DynamicComments

Fast

GF(p): 0 ≤ Input < (N2) * (232)

GF(2n): Input < ((P[x])2) * (X32)

GF(p): 0 ≤ Res < N * 4

GF(2n): Res < P[X] * (X2)

The fastest reduction available, needs a precomputed constant.

Normalized

InputLength < NLength + 4 bytes

GF(p): 0 ≤ Res < N GF(2n): Res < P[X]

The correction step does not runs in constant time. Needs a precomputed constant.

The Normalize function cannot be applied to the product of two numbers of length u2NLength.

Using Euclidean division

InputLength < 2 * NLength + 4 bytes

GF(p): 0 ≤ Res < N

GF(2n): Res < P[X]

Does not need any precomputed constant.

To be able to use these modular reduction services (except the Euclidean division), first the implementer shall call the setup service, providing the modulus as well as one free memory space for the constant (this constant is used to speed up the modular reduction). In most commands (except the modular exponentiation), the quotient is stored in the high order bytes of the number to be reduced, using only eight bytes more than the maximum size of the number to be reduced.

The following rules must be respected to ensure the modular reduction services function correctly:

  • The numbers to be reduced can have any significant length, given the fact it CANNOT BE GREATER than 2*u2ModLength + 4 bytes.
  • The modulus SHALL ALWAYS HAVE a significant length of <u2ModLength> bytes. The modulus must be provided as a <u2ModLength + 4> bytes long number, padded on the most significant side with a 32-bit word cleared to zero. Not respecting this rule leads to unexpected and wrong results from the modular reduction.
  • The normalization operation ALWAYS performs a modular reduction step, and will therefore have the same memory usage as this one.
  • The very first operation before any modular operation SHALL BE a modular setup.