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 worda
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 worda
is overridden and stores the output signals.
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 worda
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 worda
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\), ifa
is odd. The input worda
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\), ifa
is odd. The modulusm
is passed as a vector of Booleans to support large bitsizes. The input worda
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 valuehex
most-significant digits will be ignored.