Encrypted Modulo

Definition

Modulo returns the remainder of one integer divided by another, taken element by element over encrypted operands:

where each $r_i$ is the least non-negative residue — the unique integer with $0 \le r_i < |y_i|$ that is congruent to $x_i$ modulo $y_i$.

Mathematical Domain

Modulo is a non-arithmetic operation: it is nonlinear and piecewise, unlike the additions and multiplications a homomorphic scheme supports directly, which is what makes it a substantial component to build. The remainder is defined for integer operands with a nonzero divisor; a specification fixes the operand range over which it must hold — both the width of the encrypted integers and any restriction on the divisor. The kernel fixes neither the range nor the packing, and it does not mandate a scheme; a specification pins the domain and whether one modulo or many are computed at once.

Parameters Defined by Specifications

A specification narrows the general operation into a concrete problem by pinning:

• the integer domain and width (for example i32);
• the operand range over which correctness must hold, and the divisor restriction (nonzero);
• scalar versus SIMD — one modulo, or one per slot;
• the vector length $N$ in the SIMD case;
• the input and output packing, and what is measured.

Applications

Modular reduction underlies hashing, checksums, and residue-number-system arithmetic; it is a step in many number-theoretic and cryptographic routines and in any confidential computation that must wrap encrypted counters or indices into a range. As a piecewise, nonlinear primitive it is also a stress test for the nonlinear-function machinery of an FHE stack.