Modular arithmetic networks

The file mockturtle/generators/modular_arithmetic.hpp implements several functions to generate modular arithmetic networks.

Addition and Subtraction

template<class Ntk>
inline void mockturtle::modular_adder_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, std::vector<signal<Ntk>> const &b)

Creates modular adder.

Given two input words of the same size k, this function creates a circuit that computes k output signals that represent \((a + b) \bmod 2^k\). The first input word a is overridden and stores the output signals.

template<class Ntk>
inline void mockturtle::modular_adder_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, std::vector<signal<Ntk>> const &b, uint64_t m)

Creates modular adder.

Given two input words of the same size k, this function creates a circuit that computes k output signals that represent \((a + b) \bmod m\). The first input word a is overridden and stores the output signals.

template<class Ntk>
inline void mockturtle::modular_adder_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, std::vector<signal<Ntk>> const &b, std::vector<bool> const &m)

Creates modular adder.

Given two input words of the same size k, this function creates a circuit that computes k output signals that represent \((a + b) \bmod m\). The modulus m is passed as a vector of Booleans to support large bitsizes. The first input word a is overridden and stores the output signals.

template<class Ntk>
inline std::vector<signal<Ntk>> mockturtle::modular_adder(Ntk &ntk, std::vector<signal<Ntk>> const &a, std::vector<signal<Ntk>> const &b, std::vector<bool> const &m)
template<class Ntk>
inline void mockturtle::modular_adder_hiasat_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, std::vector<signal<Ntk>> const &b, uint64_t m)
template<class Ntk>
inline void mockturtle::modular_adder_hiasat_inplace(Ntk &ntk, std::vector<signal<Ntk>> &x, std::vector<signal<Ntk>> const &y, std::vector<bool> const &m)
template<class Ntk>
inline void mockturtle::modular_subtractor_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, std::vector<signal<Ntk>> const &b)

Creates modular subtractor.

Given two input words of the same size k, this function creates a circuit that computes k output signals that represent \((a - b) \bmod 2^k\). The first input word a is overridden and stores the output signals.

template<class Ntk>
inline void mockturtle::modular_subtractor_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, std::vector<signal<Ntk>> const &b, uint64_t m)

Creates modular subtractor.

Given two input words of the same size k, this function creates a circuit that computes k output signals that represent \((a - b) \bmod m\). The first input word a is overridden and stores the output signals.

template<class Ntk>
inline void mockturtle::modular_subtractor_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, std::vector<signal<Ntk>> const &b, std::vector<bool> const &m)

Creates modular subtractor.

Given two input words of the same size k, this function creates a circuit that computes k output signals that represent \((a - b) \bmod m\). The modulus m is passed as a vector of Booleans to support large bitsizes. The first input word a is overridden and stores the output signals.

template<class Ntk>
inline std::vector<signal<Ntk>> mockturtle::modular_subtractor(Ntk &ntk, std::vector<signal<Ntk>> const &a, std::vector<signal<Ntk>> const &b, std::vector<bool> const &m)

Multiplication

template<class Ntk>
inline void mockturtle::modular_multiplication_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, std::vector<signal<Ntk>> const &b, uint64_t m)

Creates modular multiplier.

Given two inputs words of the same size k, this function creates a circuit that computes k output signals that represent \((ab) \bmod c\). The first input word a is overridden and stores the output signals.

template<class Ntk>
inline void mockturtle::modular_multiplication_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, std::vector<signal<Ntk>> const &b, std::vector<bool> const &m)

Creates modular multiplication.

Given two inputs words of the same size k, this function creates a circuit that computes k output signals that represent \((ab) \bmod c\). The modulus m is passed as a vector of Booleans to support large bitsizes. The first input word a is overridden and stores the output signals.

template<class Ntk>
inline std::vector<signal<Ntk>> mockturtle::modular_multiplication(Ntk &ntk, std::vector<signal<Ntk>> const &a, std::vector<signal<Ntk>> const &b, std::vector<bool> const &m)
template<class Ntk>
inline void mockturtle::modular_doubling_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, uint64_t m)

Creates modular doubling (multiplication by 2)

Given one input word \(a\) of size k, this function creates a circuit that computes k output signals that represent \((2 * a) \bmod m\). The input word a is overridden and stores the output signals.

template<class Ntk>
inline void mockturtle::modular_doubling_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, std::vector<bool> const &m)

Creates modular doubling (multiplication by 2)

Given one input word \(a\) of size k, this function creates a circuit that computes k output signals that represent \((2 * a) \bmod m\). The modulus m is passed as a vector of Booleans to support large bitsizes. The input word a is overridden and stores the output signals.

template<class Ntk>
inline void mockturtle::modular_halving_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, uint64_t m)

Creates modular halving (corrected division by 2)

Given one input word \(a\) of size k, this function creates a circuit that computes k output signals that represent \((a / 2) \bmod m\). The modulus must be odd, and the function is evaluated to \(a / 2\), if a is even and to \((a + m) / 2\), if a is odd. The input word a is overridden and stores the output signals.

template<class Ntk>
inline void mockturtle::modular_halving_inplace(Ntk &ntk, std::vector<signal<Ntk>> &a, std::vector<bool> const &m)

Creates modular halving (corrected division by 2)

Given one input word \(a\) of size k, this function creates a circuit that computes k output signals that represent \((a / 2) \bmod m\). The modulus must be odd, and the function is evaluated to \(a / 2\), if a is even and to \((a + m) / 2\), if a is odd. The modulus m is passed as a vector of Booleans to support large bitsizes. The input word a is overridden and stores the output signals.

template<class Ntk>
inline std::vector<signal<Ntk>> mockturtle::modular_constant_multiplier(Ntk &ntk, std::vector<signal<Ntk>> const &a, std::vector<bool> const &constant)

Creates modular constant-multiplier.

Given an input word of size k and a constant with the same bit-width, this function creates a circuit that computes \((a\cdot\mathrm{constant}) \bmod 2^k\).

template<class Ntk>
inline std::vector<signal<Ntk>> mockturtle::montgomery_multiplication(Ntk &ntk, std::vector<signal<Ntk>> const &a, std::vector<signal<Ntk>> const &b, std::vector<bool> const &N, std::vector<bool> const &NN)

Creates a multiplier assuming Montgomery numbers as inputs.

This modular multiplication assumes the two inputs a and b to be Montgomery numbers representing \(a \cdot 2^k \bmod N\), where \(N\) is the modulus as bit-string, and \(k\) is the bit-width of a and b. It returns a signal of length b. The last paramaeter NN must be computed such that \(R \cdot 2^k = N \cdot NN\) using the extended GCD.

template<class Ntk>
inline std::vector<signal<Ntk>> mockturtle::montgomery_multiplication(Ntk &ntk, std::vector<signal<Ntk>> const &a, std::vector<signal<Ntk>> const &b, uint64_t N)

Creates a multiplier assuming Montgomery numbers as inputs.

This modular multiplication assumes the two inputs a and b to be Montgomery numbers representing \(a \cdot 2^k \bmod N\), where \(N\) is the modulus, and \(k\) is the bit-width of a and b. It returns a signal of length b.

Utility functions

inline void mockturtle::bool_vector_from_hex(std::vector<bool> &res, std::string_view hex, bool shrink_to_fit = true)

Creates vector of Booleans from hex string.

This function can be used to create moduli for very large numbers that cannot be represented using any of the integer built-in data types. If the vector res is too small for the value hex most-significant digits will be ignored.