Binary division

concrete_fhe_toolkit.math.binary_division

Binary restoring division helpers for Concrete FHE circuits.

unsigned_divide_bits

unsigned_divide_bits(numerator_bits: Iterable[Any], denominator_bits: Iterable[Any], *, quotient_width: int | None = None, zero_result: int = 0) -> tuple[Any, ...]

Return little-endian quotient bits for unsigned floor division.

Division by zero returns the clear fallback encoded by zero_result.

Parameters:

Name	Type	Description	Default
numerator_bits	Iterable[...]	An iterable of encrypted or cleartext bits representing the numerator in little-endian format.	required
denominator_bits	Iterable[...]	An iterable of encrypted or cleartext bits representing the denominator in little-endian format.	required

Returns:

Type	Description
tuple[Any, ...]	tuple[...]: The resulting value.

Example

from concrete_fhe_toolkit.math.binary_division import unsigned_divide_bits

num_bits = [1, 0, 1]  # 5
den_bits = [0, 1]     # 2
# Use `unsigned_divide_bits(num_bits, den_bits)` inside an FHE program compilation

Source code in src/concrete_fhe_toolkit/math/binary_division.py

def unsigned_divide_bits(
    numerator_bits: Iterable[Any],
    denominator_bits: Iterable[Any],
    *,
    quotient_width: int | None = None,
    zero_result: int = 0,
) -> tuple[Any, ...]:
    """Return little-endian quotient bits for unsigned floor division.

    Division by zero returns the clear fallback encoded by `zero_result`.

    Args:
        numerator_bits (Iterable[...]): An iterable of encrypted or cleartext bits representing the numerator in little-endian format.
        denominator_bits (Iterable[...]): An iterable of encrypted or cleartext bits representing the denominator in little-endian format.

    Returns:
        tuple[...]: The resulting value.

    Example:
        ```python
        from concrete_fhe_toolkit.math.binary_division import unsigned_divide_bits

        num_bits = [1, 0, 1]  # 5
        den_bits = [0, 1]     # 2
        # Use `unsigned_divide_bits(num_bits, den_bits)` inside an FHE program compilation
        ```
    """
    numerator = _as_nonempty_bits("numerator_bits", numerator_bits)
    denominator = _as_nonempty_bits("denominator_bits", denominator_bits)
    width = (
        len(numerator)
        if quotient_width is None
        else _validate_width("quotient_width", quotient_width)
    )
    if len(numerator) > width:
        raise ValueError("quotient_width must be at least len(numerator_bits)")
    zero = _validate_zero_result(zero_result, width)

    quotient, _ = _restoring_divide_bits(numerator, denominator, width)
    denominator_nonzero = bit_or_many(denominator)
    fallback = unsigned_to_bits(zero, width)
    return tuple(
        bit_select(denominator_nonzero, quotient[index], fallback[index])
        for index in range(width)
    )

fixed_point_divide_bits

fixed_point_divide_bits(numerator_bits: Iterable[Any], denominator_bits: Iterable[Any], *, fractional_bits: int, quotient_width: int | None = None, zero_result: int = 0) -> tuple[Any, ...]

Return quotient bits for floor((numerator << fractional_bits) / denominator).

Parameters:

Name	Type	Description	Default
numerator_bits	Iterable[...]	An iterable of encrypted or cleartext bits representing the numerator in little-endian format.	required
denominator_bits	Iterable[...]	An iterable of encrypted or cleartext bits representing the denominator in little-endian format.	required

Returns:

Type	Description
tuple[Any, ...]	tuple[...]: The resulting value.

Example

from concrete_fhe_toolkit.math.binary_division import fixed_point_divide_bits

num_bits = [1, 0, 1]  # 5
den_bits = [0, 1]     # 2
# Use `fixed_point_divide_bits(num_bits, den_bits, fractional_bits=1)` inside an FHE program compilation

Source code in src/concrete_fhe_toolkit/math/binary_division.py

def fixed_point_divide_bits(
    numerator_bits: Iterable[Any],
    denominator_bits: Iterable[Any],
    *,
    fractional_bits: int,
    quotient_width: int | None = None,
    zero_result: int = 0,
) -> tuple[Any, ...]:
    """Return quotient bits for floor((numerator << fractional_bits) / denominator).

    Args:
        numerator_bits (Iterable[...]): An iterable of encrypted or cleartext bits representing the numerator in little-endian format.
        denominator_bits (Iterable[...]): An iterable of encrypted or cleartext bits representing the denominator in little-endian format.

    Returns:
        tuple[...]: The resulting value.

    Example:
        ```python
        from concrete_fhe_toolkit.math.binary_division import fixed_point_divide_bits

        num_bits = [1, 0, 1]  # 5
        den_bits = [0, 1]     # 2
        # Use `fixed_point_divide_bits(num_bits, den_bits, fractional_bits=1)` inside an FHE program compilation
        ```
    """
    numerator = _as_nonempty_bits("numerator_bits", numerator_bits)
    fraction = _validate_fractional_bits(fractional_bits)
    shifted_numerator = (0,) * fraction + numerator
    width = (
        len(shifted_numerator)
        if quotient_width is None
        else _validate_width("quotient_width", quotient_width)
    )
    if len(shifted_numerator) > width:
        raise ValueError(
            "quotient_width must be at least len(numerator_bits) + fractional_bits"
        )
    return unsigned_divide_bits(
        shifted_numerator,
        denominator_bits,
        quotient_width=width,
        zero_result=zero_result,
    )

make_unsigned_floor_divide

make_unsigned_floor_divide(numerator_width: int, denominator_width: int, *, quotient_width: int | None = None, zero_result: int = 0) -> Any

Create unsigned encrypted floor division from scalar integer inputs.

Parameters:

Name	Type	Description	Default
numerator_width	int	The bit width of the numerator.	required
denominator_width	int	The bit width of the denominator.	required

Returns:

Name	Type	Description
Any	Any	The resulting value.

Example

from concrete_fhe_toolkit.math.binary_division import make_unsigned_floor_divide

div_fn = make_unsigned_floor_divide(numerator_width=4, denominator_width=4)
# Use `div_fn(num, den)` inside an FHE program compilation

Source code in src/concrete_fhe_toolkit/math/binary_division.py

def make_unsigned_floor_divide(
    numerator_width: int,
    denominator_width: int,
    *,
    quotient_width: int | None = None,
    zero_result: int = 0,
) -> Any:
    """Create unsigned encrypted floor division from scalar integer inputs.

    Args:
        numerator_width (int): The bit width of the numerator.
        denominator_width (int): The bit width of the denominator.

    Returns:
        Any: The resulting value.

    Example:
        ```python
        from concrete_fhe_toolkit.math.binary_division import make_unsigned_floor_divide

        div_fn = make_unsigned_floor_divide(numerator_width=4, denominator_width=4)
        # Use `div_fn(num, den)` inside an FHE program compilation
        ```
    """
    n_width = _validate_width("numerator_width", numerator_width)
    d_width = _validate_width("denominator_width", denominator_width)
    q_width = (
        n_width
        if quotient_width is None
        else _validate_width("quotient_width", quotient_width)
    )
    if q_width < n_width:
        raise ValueError("quotient_width must be at least numerator_width")
    zero = _validate_zero_result(zero_result, q_width)

    def divide(numerator: Any, denominator: Any) -> Any:
        """Execute the unsigned floor division circuit on inputs.

        Args:
            numerator: The encrypted dividend/numerator.
            denominator: The encrypted divisor/denominator.

        Returns:
            The unsigned integer result of the floor division.
        """
        numerator_bits = integer_to_bits(numerator, n_width)
        denominator_bits = integer_to_bits(denominator, d_width)
        quotient_bits = unsigned_divide_bits(
            numerator_bits,
            denominator_bits,
            quotient_width=q_width,
            zero_result=zero,
        )
        return bits_to_unsigned(quotient_bits)

    return divide

make_fixed_point_divide

make_fixed_point_divide(numerator_width: int, denominator_width: int, *, fractional_bits: int, quotient_width: int | None = None, zero_result: int = 0) -> Any

Create fixed-point unsigned division from scalar integer inputs.

Parameters:

Name	Type	Description	Default
numerator_width	int	The bit width of the numerator.	required
denominator_width	int	The bit width of the denominator.	required

Returns:

Name	Type	Description
Any	Any	The resulting value.

Example

from concrete_fhe_toolkit.math.binary_division import make_fixed_point_divide

div_fn = make_fixed_point_divide(4, 4, fractional_bits=2)
# Use `div_fn(num, den)` inside an FHE program compilation

Source code in src/concrete_fhe_toolkit/math/binary_division.py

def make_fixed_point_divide(
    numerator_width: int,
    denominator_width: int,
    *,
    fractional_bits: int,
    quotient_width: int | None = None,
    zero_result: int = 0,
) -> Any:
    """Create fixed-point unsigned division from scalar integer inputs.

    Args:
        numerator_width (int): The bit width of the numerator.
        denominator_width (int): The bit width of the denominator.

    Returns:
        Any: The resulting value.

    Example:
        ```python
        from concrete_fhe_toolkit.math.binary_division import make_fixed_point_divide

        div_fn = make_fixed_point_divide(4, 4, fractional_bits=2)
        # Use `div_fn(num, den)` inside an FHE program compilation
        ```
    """
    n_width = _validate_width("numerator_width", numerator_width)
    d_width = _validate_width("denominator_width", denominator_width)
    fraction = _validate_fractional_bits(fractional_bits)
    default_width = n_width + fraction
    q_width = (
        default_width
        if quotient_width is None
        else _validate_width("quotient_width", quotient_width)
    )
    if q_width < default_width:
        raise ValueError(
            "quotient_width must be at least numerator_width + fractional_bits"
        )
    zero = _validate_zero_result(zero_result, q_width)

    def divide(numerator: Any, denominator: Any) -> Any:
        """Execute the fixed-point division circuit on inputs.

        Args:
            numerator: The encrypted dividend/numerator.
            denominator: The encrypted divisor/denominator.

        Returns:
            The unsigned integer fixed-point division result.
        """
        numerator_bits = integer_to_bits(numerator, n_width)
        denominator_bits = integer_to_bits(denominator, d_width)
        quotient_bits = fixed_point_divide_bits(
            numerator_bits,
            denominator_bits,
            fractional_bits=fraction,
            quotient_width=q_width,
            zero_result=zero,
        )
        return bits_to_unsigned(quotient_bits)

    return divide

compile_unsigned_floor_divide

compile_unsigned_floor_divide(numerator_width: int, denominator_width: int, *, quotient_width: int | None = None, zero_result: int = 0, configuration: Optional[Configuration] = None) -> fhe.Circuit

Compile unsigned floor division using a bit-level restoring circuit.

Parameters:

Name	Type	Description	Default
numerator_width	int	The bit width of the numerator.	required
denominator_width	int	The bit width of the denominator.	required

Returns:

Name	Type	Description
Any	Circuit	The resulting value.

Example

from concrete_fhe_toolkit.math.binary_division import compile_unsigned_floor_divide

circuit = compile_unsigned_floor_divide(numerator_width=4, denominator_width=4)
print(circuit.encrypt_run_decrypt(10, 3))  # 3

Source code in src/concrete_fhe_toolkit/math/binary_division.py

def compile_unsigned_floor_divide(
    numerator_width: int,
    denominator_width: int,
    *,
    quotient_width: int | None = None,
    zero_result: int = 0,
    configuration: Optional[fhe.Configuration] = None,
) -> fhe.Circuit:
    """Compile unsigned floor division using a bit-level restoring circuit.

    Args:
        numerator_width (int): The bit width of the numerator.
        denominator_width (int): The bit width of the denominator.

    Returns:
        Any: The resulting value.

    Example:
        ```python
        from concrete_fhe_toolkit.math.binary_division import compile_unsigned_floor_divide

        circuit = compile_unsigned_floor_divide(numerator_width=4, denominator_width=4)
        print(circuit.encrypt_run_decrypt(10, 3))  # 3
        ```
    """
    n_width = _validate_width("numerator_width", numerator_width)
    d_width = _validate_width("denominator_width", denominator_width)
    function = make_unsigned_floor_divide(
        n_width,
        d_width,
        quotient_width=quotient_width,
        zero_result=zero_result,
    )
    return compile_function(
        function,
        {"numerator": "encrypted", "denominator": "encrypted"},
        _division_inputset(n_width, d_width),
        configuration,
    )

compile_fixed_point_divide

compile_fixed_point_divide(numerator_width: int, denominator_width: int, *, fractional_bits: int, quotient_width: int | None = None, zero_result: int = 0, configuration: Optional[Configuration] = None) -> fhe.Circuit

Compile fixed-point unsigned division using a bit-level circuit.

Parameters:

Name	Type	Description	Default
numerator_width	int	The bit width of the numerator.	required
denominator_width	int	The bit width of the denominator.	required

Returns:

Name	Type	Description
Any	Circuit	The resulting value.

Example

from concrete_fhe_toolkit.math.binary_division import compile_fixed_point_divide

circuit = compile_fixed_point_divide(4, 4, fractional_bits=2)
print(circuit.encrypt_run_decrypt(5, 2))  # floor((5 << 2) / 2) = 10

Source code in src/concrete_fhe_toolkit/math/binary_division.py

def compile_fixed_point_divide(
    numerator_width: int,
    denominator_width: int,
    *,
    fractional_bits: int,
    quotient_width: int | None = None,
    zero_result: int = 0,
    configuration: Optional[fhe.Configuration] = None,
) -> fhe.Circuit:
    """Compile fixed-point unsigned division using a bit-level circuit.

    Args:
        numerator_width (int): The bit width of the numerator.
        denominator_width (int): The bit width of the denominator.

    Returns:
        Any: The resulting value.

    Example:
        ```python
        from concrete_fhe_toolkit.math.binary_division import compile_fixed_point_divide

        circuit = compile_fixed_point_divide(4, 4, fractional_bits=2)
        print(circuit.encrypt_run_decrypt(5, 2))  # floor((5 << 2) / 2) = 10
        ```
    """
    n_width = _validate_width("numerator_width", numerator_width)
    d_width = _validate_width("denominator_width", denominator_width)
    function = make_fixed_point_divide(
        n_width,
        d_width,
        fractional_bits=fractional_bits,
        quotient_width=quotient_width,
        zero_result=zero_result,
    )
    return compile_function(
        function,
        {"numerator": "encrypted", "denominator": "encrypted"},
        _division_inputset(n_width, d_width),
        configuration,
    )

unsigned_mod_bits

unsigned_mod_bits(numerator_bits: Iterable[Any], denominator_bits: Iterable[Any], *, zero_result: int = 0) -> tuple[Any, ...]

Return little-endian remainder bits for unsigned modulo.

The remainder always fits in the denominator's bit width. Division by zero returns the clear fallback encoded by zero_result.

Parameters:

Name	Type	Description	Default
numerator_bits	Iterable[...]	An iterable of encrypted or cleartext bits representing the numerator in little-endian format.	required
denominator_bits	Iterable[...]	An iterable of encrypted or cleartext bits representing the denominator in little-endian format.	required

Returns:

Type	Description
tuple[Any, ...]	tuple[...]: The resulting value.

Example

from concrete_fhe_toolkit.math.binary_division import unsigned_mod_bits

num_bits = [1, 0, 1]  # 5
den_bits = [0, 1]     # 2
# Use `unsigned_mod_bits(num_bits, den_bits)` inside an FHE program compilation

Source code in src/concrete_fhe_toolkit/math/binary_division.py

def unsigned_mod_bits(
    numerator_bits: Iterable[Any],
    denominator_bits: Iterable[Any],
    *,
    zero_result: int = 0,
) -> tuple[Any, ...]:
    """Return little-endian remainder bits for unsigned modulo.

    The remainder always fits in the denominator's bit width. Division by
    zero returns the clear fallback encoded by ``zero_result``.

    Args:
        numerator_bits (Iterable[...]): An iterable of encrypted or cleartext bits representing the numerator in little-endian format.
        denominator_bits (Iterable[...]): An iterable of encrypted or cleartext bits representing the denominator in little-endian format.

    Returns:
        tuple[...]: The resulting value.

    Example:
        ```python
        from concrete_fhe_toolkit.math.binary_division import unsigned_mod_bits

        num_bits = [1, 0, 1]  # 5
        den_bits = [0, 1]     # 2
        # Use `unsigned_mod_bits(num_bits, den_bits)` inside an FHE program compilation
        ```
    """
    numerator = _as_nonempty_bits("numerator_bits", numerator_bits)
    denominator = _as_nonempty_bits("denominator_bits", denominator_bits)
    width = len(denominator)
    zero = _validate_zero_result(zero_result, width)

    _, remainder = _restoring_divide_bits(numerator, denominator, len(numerator))
    denominator_nonzero = bit_or_many(denominator)
    fallback = unsigned_to_bits(zero, width)
    return tuple(
        bit_select(denominator_nonzero, remainder[index], fallback[index])
        for index in range(width)
    )

make_unsigned_mod

make_unsigned_mod(numerator_width: int, denominator_width: int, *, zero_result: int = 0) -> Any

Create unsigned encrypted modulo from scalar integer inputs.

Parameters:

Name	Type	Description	Default
numerator_width	int	The bit width of the numerator.	required
denominator_width	int	The bit width of the denominator.	required

Returns:

Name	Type	Description
Any	Any	The resulting value.

Example

from concrete_fhe_toolkit.math.binary_division import make_unsigned_mod

mod_fn = make_unsigned_mod(numerator_width=4, denominator_width=4)
# Use `mod_fn(num, den)` inside an FHE program compilation

Source code in src/concrete_fhe_toolkit/math/binary_division.py

def make_unsigned_mod(
    numerator_width: int,
    denominator_width: int,
    *,
    zero_result: int = 0,
) -> Any:
    """Create unsigned encrypted modulo from scalar integer inputs.

    Args:
        numerator_width (int): The bit width of the numerator.
        denominator_width (int): The bit width of the denominator.

    Returns:
        Any: The resulting value.

    Example:
        ```python
        from concrete_fhe_toolkit.math.binary_division import make_unsigned_mod

        mod_fn = make_unsigned_mod(numerator_width=4, denominator_width=4)
        # Use `mod_fn(num, den)` inside an FHE program compilation
        ```
    """
    n_width = _validate_width("numerator_width", numerator_width)
    d_width = _validate_width("denominator_width", denominator_width)
    zero = _validate_zero_result(zero_result, d_width)

    def modulo(numerator: Any, denominator: Any) -> Any:
        """Execute the unsigned modulo circuit on inputs.

        Args:
            numerator: The encrypted dividend/numerator.
            denominator: The encrypted divisor/denominator.

        Returns:
            The remainder of the unsigned division.
        """
        numerator_bits = integer_to_bits(numerator, n_width)
        denominator_bits = integer_to_bits(denominator, d_width)
        remainder_bits = unsigned_mod_bits(
            numerator_bits,
            denominator_bits,
            zero_result=zero,
        )
        return bits_to_unsigned(remainder_bits)

    return modulo

compile_unsigned_mod

compile_unsigned_mod(numerator_width: int, denominator_width: int, *, zero_result: int = 0, configuration: Optional[Configuration] = None) -> fhe.Circuit

Compile unsigned modulo using the bit-level restoring circuit.

Parameters:

Name	Type	Description	Default
numerator_width	int	The bit width of the numerator.	required
denominator_width	int	The bit width of the denominator.	required

Returns:

Name	Type	Description
Any	Circuit	The resulting value.

Example

from concrete_fhe_toolkit.math.binary_division import compile_unsigned_mod

circuit = compile_unsigned_mod(numerator_width=4, denominator_width=4)
print(circuit.encrypt_run_decrypt(10, 3))  # 1

Source code in src/concrete_fhe_toolkit/math/binary_division.py

def compile_unsigned_mod(
    numerator_width: int,
    denominator_width: int,
    *,
    zero_result: int = 0,
    configuration: Optional[fhe.Configuration] = None,
) -> fhe.Circuit:
    """Compile unsigned modulo using the bit-level restoring circuit.

    Args:
        numerator_width (int): The bit width of the numerator.
        denominator_width (int): The bit width of the denominator.

    Returns:
        Any: The resulting value.

    Example:
        ```python
        from concrete_fhe_toolkit.math.binary_division import compile_unsigned_mod

        circuit = compile_unsigned_mod(numerator_width=4, denominator_width=4)
        print(circuit.encrypt_run_decrypt(10, 3))  # 1
        ```
    """
    n_width = _validate_width("numerator_width", numerator_width)
    d_width = _validate_width("denominator_width", denominator_width)
    function = make_unsigned_mod(
        n_width,
        d_width,
        zero_result=zero_result,
    )
    return compile_function(
        function,
        {"numerator": "encrypted", "denominator": "encrypted"},
        _division_inputset(n_width, d_width),
        configuration,
    )