Skip to content

Modular arithmetic

Modular values make the modulus part of the numeric type or context. Arithmetic preserves that modulus and does not silently mix incompatible values.

Design documentation

This chapter describes the language design. Examples are illustrative; implementation availability and unresolved rules are explained in Design status.

Representation and operations

Integers modulo a positive integer are first-class numeric values. Names and syntax are provisional:

type Mod17 = ModInt[17]
let x = Mod17(15)
let y = Mod17(5)
let sum = x + y          // 3 modulo 17
let product = x * y      // 7 modulo 17
  • Representatives are canonical in [0, n).
  • Construction reduces arbitrary integers, including negative values.
  • Addition, subtraction, multiplication, negation, and nonnegative integer powers preserve the modulus.
  • Intermediate fixed-width overflow must not corrupt modular results.
  • Different moduli cannot mix implicitly.
  • Equality and hashing include the modulus.
  • There is no intrinsic order; ordering representatives requires explicit access.
  • Inversion is partial: a nonzero element need not be invertible.
  • try_inverse() reports absence ordinarily; inverse() declares NonInvertibleError. Division multiplies by the inverse.

Compile-time moduli permit specialized representations and arithmetic. Runtime moduli use shared immutable contexts with precomputed reduction parameters. Large moduli can use bigint. Small values should avoid heap allocation.

Fast modular arithmetic does not imply constant-time cryptographic arithmetic. Cryptographic timing guarantees require a separate explicit contract.

Inversion is not ordinary division

For modulus 6, the nonzero value 2 has no multiplicative inverse: no integer multiplied by 2 has representative 1 modulo 6. The value 5 does have an inverse, because 5 * 5 has representative 1. Use the absence-reporting operation when non-invertibility is expected, and the declared-exception operation when a missing inverse is an operational failure.

A modular type's convenient arithmetic does not establish any cryptographic timing guarantee. Such a guarantee needs its own explicit contract.