13#ifndef BOTAN_PQ_CRYSTALS_H_
14#define BOTAN_PQ_CRYSTALS_H_
21#include <botan/assert.h>
22#include <botan/mem_ops.h>
23#include <botan/internal/ct_utils.h>
24#include <botan/internal/pqcrystals_helpers.h>
32 std::signed_integral<typename T::T> && std::integral<
decltype(T::N)> && std::integral<
decltype(T::Q)> &&
33 std::integral<
decltype(T::F)> && std::unsigned_integral<
decltype(T::NTT_Degree)> &&
34 std::integral<
decltype(T::ROOT_OF_UNITY)>;
48template <crystals_constants ConstantsT,
typename DerivedT>
51 using T =
typename ConstantsT::T;
52 static constexpr T N = ConstantsT::N;
53 static constexpr T Q = ConstantsT::Q;
75 static constexpr auto zetas = precompute_zetas<ConstantsT::NTT_Degree>(
Q,
MONTY, ConstantsT::ROOT_OF_UNITY);
85 return polyvec.size() /
N;
90 requires(std::same_as<T, U> || std::same_as<const T, U>)
91 static constexpr std::span<U, N>
poly_in_polyvec(std::span<U> polyvec,
size_t index) {
94 const auto polyspan = polyvec.subspan(index *
N,
N);
95 return std::span<U, N>{polyspan.data(), polyspan.size()};
98 static constexpr T fqmul(
T a,
T b) {
return DerivedT::montgomery_reduce_coefficient(
static_cast<T2>(a) * b); }
101 static constexpr void poly_add(std::span<T, N> result, std::span<const T, N> lhs, std::span<const T, N> rhs) {
102 for(
size_t i = 0; i <
N; ++i) {
103 result[i] = lhs[i] + rhs[i];
107 static constexpr void poly_sub(std::span<T, N> result, std::span<const T, N> lhs, std::span<const T, N> rhs) {
108 for(
size_t i = 0; i <
N; ++i) {
109 result[i] = lhs[i] - rhs[i];
115 for(
auto& coeff : coeffs) {
116 using unsigned_T = std::make_unsigned_t<T>;
118 coeff += is_negative.if_set_return(
Q);
125 for(
auto& coeff : poly) {
126 coeff = DerivedT::barrett_reduce_coefficient(coeff);
132 std::span<const T> u,
133 std::span<const T> v) {
135 std::array<T, N> t{};
146 std::signed_integral<typename T::T> &&
sizeof(
typename T::T) <= 4 && std::integral<
decltype(T::N)> &&
148 requires(std::span<typename T::T, T::N> polyspan, std::span<typename T::T> polyvecspan,
typename T::T coeff) {
149 { T::to_montgomery(coeff) };
150 { T::barrett_reduce(polyspan) };
151 { T::poly_cadd_q(polyspan) };
152 { T::ntt(polyspan) };
153 { T::inverse_ntt(polyspan) };
154 { T::poly_pointwise_montgomery(polyspan, polyspan, polyspan) };
155 { T::polyvec_pointwise_acc_montgomery(polyspan, polyvecspan, polyvecspan) };
163template <Domain To,
template <
typename, Domain>
class StructureT,
crystals_trait Trait,
Domain From>
169 return StructureT<Trait, To>::from_domain_cast(std::move(p));
178template <std::
integral T,
size_t N = std::dynamic_extent>
179constexpr static bool ct_all_within_range(std::span<const T, N> range, T min, T max)
180 requires(
sizeof(T) <= 4)
184 using unsigned_T = std::make_unsigned_t<T>;
185 const auto map = [](T v) -> unsigned_T {
186 if constexpr(std::signed_integral<T>) {
187 constexpr int64_t offset = -
static_cast<int64_t
>(std::numeric_limits<T>::min());
188 return static_cast<unsigned_T
>(
static_cast<int64_t
>(v) + offset);
194 const auto umin = map(min);
195 const auto umax = map(max);
198 for(
const T c : range) {
201 return mask.as_bool();
214template <crystals_trait Trait, Domain D = Domain::Normal>
218 using T =
typename Trait::T;
222 std::vector<T> m_coeffs_storage;
223 std::span<T, Trait::N> m_coeffs;
226 template <crystals_trait OtherTrait, Domain OtherD>
229 template <Domain To,
template <
typename, Domain>
class StructureT,
crystals_trait C,
Domain From>
237 template <Domain OtherD>
238 requires(D != OtherD)
240 m_coeffs_storage(std::move(other.m_coeffs_storage)),
241 m_coeffs(
owns_storage() ? std::span<T, Trait::N>(m_coeffs_storage) : other.m_coeffs) {}
249 template <Domain OtherD>
250 requires(D != OtherD)
263 m_coeffs_storage(std::move(other.m_coeffs_storage)), m_coeffs(other.m_coeffs) {}
265 ThisPolynomial&
operator=(
const ThisPolynomial& other) =
delete;
267 ThisPolynomial&
operator=(ThisPolynomial&& other)
noexcept {
270 m_coeffs_storage = std::move(other.m_coeffs_storage);
271 m_coeffs = std::span<T, Trait::N>(m_coeffs_storage);
278 constexpr size_t size()
const {
return m_coeffs.size(); }
284 copy_mem(res.m_coeffs_storage, m_coeffs);
285 res.m_coeffs = std::span<T, Trait::N>(res.m_coeffs_storage);
292 return detail::ct_all_within_range(
coefficients(), min, max);
298 for(
const auto c : m_coeffs) {
312 decltype(
auto)
begin() {
return m_coeffs.begin(); }
314 decltype(
auto)
begin()
const {
return m_coeffs.begin(); }
316 decltype(
auto)
end() {
return m_coeffs.end(); }
318 decltype(
auto)
end()
const {
return m_coeffs.end(); }
320 constexpr bool owns_storage()
const {
return !m_coeffs_storage.empty(); }
323 Trait::barrett_reduce(m_coeffs);
328 Trait::poly_cadd_q(m_coeffs);
340 decltype(
auto)
operator+=(
const ThisPolynomial& other) {
341 Trait::poly_add(m_coeffs, m_coeffs, other.m_coeffs);
349 decltype(
auto)
operator-=(
const ThisPolynomial& other) {
350 Trait::poly_sub(m_coeffs, m_coeffs, other.m_coeffs);
355template <crystals_trait Trait, Domain D = Domain::Normal>
359 using T =
typename Trait::T;
362 std::vector<T> m_polys_storage;
363 std::vector<Polynomial<Trait, D>> m_vec;
366 template <crystals_trait OtherTrait, Domain OtherD>
369 template <Domain To,
template <
typename, Domain>
class StructureT,
crystals_trait C,
Domain From>
377 template <Domain OtherD>
378 requires(D != OtherD)
381 m_polys_storage(std::move(other.m_polys_storage)) {
383 const size_t vecsize = m_polys_storage.size() / Trait::N;
384 for(
size_t i = 0; i < vecsize; ++i) {
386 Polynomial<Trait, D>(std::span{m_polys_storage}.subspan(i * Trait::N).
template first<Trait::N>()));
396 template <Domain OtherD>
397 requires(D != OtherD)
404 for(
size_t i = 0; i < vecsize; ++i) {
406 Polynomial<Trait, D>(std::span{m_polys_storage}.subspan(i * Trait::N).
template first<Trait::N>()));
412 ThisPolynomialVector&
operator=(
const ThisPolynomialVector& other) =
delete;
413 ThisPolynomialVector&
operator=(ThisPolynomialVector&& other)
noexcept =
default;
416 size_t size()
const {
return m_vec.size(); }
420 ThisPolynomialVector
clone()
const {
421 ThisPolynomialVector res(
size());
426 copy_mem(res.m_polys_storage, m_polys_storage);
434 for(
const auto c : m_polys_storage) {
442 return detail::ct_all_within_range(
coefficients(), min, max);
449 ThisPolynomialVector&
operator+=(
const ThisPolynomialVector& other) {
450 BOTAN_ASSERT(m_vec.size() == other.m_vec.size(),
"cannot add polynomial vectors of differing lengths");
451 for(
size_t i = 0; i < m_vec.size(); ++i) {
457 ThisPolynomialVector&
operator-=(
const ThisPolynomialVector& other) {
458 BOTAN_ASSERT(m_vec.size() == other.m_vec.size(),
"cannot subtract polynomial vectors of differing lengths");
459 for(
size_t i = 0; i < m_vec.size(); ++i) {
466 for(
auto& p : m_vec) {
467 Trait::barrett_reduce(p.coefficients());
473 for(
auto& v : m_vec) {
474 Trait::poly_cadd_q(v.coefficients());
485 std::vector<Polynomial<Trait, D>*> result;
486 result.reserve(m_vec.size());
487 for(
auto& p : m_vec) {
488 result.push_back(&p);
493 decltype(
auto)
begin() {
return m_vec.begin(); }
495 decltype(
auto)
begin()
const {
return m_vec.begin(); }
497 decltype(
auto)
end() {
return m_vec.end(); }
499 decltype(
auto)
end()
const {
return m_vec.end(); }
506template <crystals_trait Trait>
512 std::vector<PolynomialVector<Trait, Domain::NTT>> m_mat;
519 ThisPolynomialMatrix&
operator=(
const ThisPolynomialMatrix& other) =
delete;
520 ThisPolynomialMatrix&
operator=(ThisPolynomialMatrix&& other)
noexcept =
default;
523 size_t size()
const {
return m_mat.size(); }
527 for(
size_t i = 0; i < rows; ++i) {
528 m_mat.emplace_back(cols);
536 decltype(
auto)
begin() {
return m_mat.begin(); }
538 decltype(
auto)
begin()
const {
return m_mat.begin(); }
540 decltype(
auto)
end() {
return m_mat.end(); }
542 decltype(
auto)
end()
const {
return m_mat.end(); }
551template <crystals_trait Trait, Domain D>
554 c = Trait::to_montgomery(c);
558template <crystals_trait Trait>
563 for(
size_t i = 0; i < a.
size(); ++i) {
571template <crystals_trait Trait>
574 Trait::ntt(p_ntt.coefficients());
578template <crystals_trait Trait>
581 Trait::inverse_ntt(p.coefficients());
585template <crystals_trait Trait>
588 for(
auto& poly : polyvec_ntt) {
589 Trait::ntt(poly.coefficients());
594template <crystals_trait Trait>
597 for(
auto& poly : polyvec) {
598 Trait::inverse_ntt(poly.coefficients());
603template <crystals_trait Trait, Domain D>
609template <crystals_trait Trait, Domain D>
611 for(
auto& p : polyvec) {
617template <crystals_trait Trait>
622 for(
size_t i = 0; i < a.
size(); ++i) {
623 Trait::poly_add(result[i].coefficients(), a[i].coefficients(), b[i].coefficients());
628template <crystals_trait Trait>
632 for(
size_t i = 0; i < mat.
size(); ++i) {
633 Trait::polyvec_pointwise_acc_montgomery(result[i].coefficients(), mat[i].coefficients(), vec.
coefficients());
638template <crystals_trait Trait>
646template <crystals_trait Trait>
650 for(
size_t i = 0; i < pv.
size(); ++i) {
656template <crystals_trait Trait>
664template <crystals_trait Trait>
665PolynomialVector<Trait, Domain::Normal>
operator<<(
const PolynomialVector<Trait, Domain::Normal>& pv,
size_t shift) {
667 PolynomialVector<Trait, Domain::Normal> result(pv.size());
668 for(
size_t i = 0; i < pv.size(); ++i) {
669 for(
size_t j = 0; j < Trait::N; ++j) {
670 result[i][j] = pv[i][j] << shift;
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ASSERT(expr, assertion_made)
PolynomialMatrix(size_t rows, size_t cols)
PolynomialVector< Trait, Domain::NTT > & operator[](size_t i)
PolynomialMatrix(ThisPolynomialMatrix &&other) noexcept=default
ThisPolynomialMatrix & operator=(const ThisPolynomialMatrix &other)=delete
decltype(auto) end() const
void _const_time_poison() const
PolynomialMatrix(const ThisPolynomialMatrix &other)=delete
const PolynomialVector< Trait, Domain::NTT > & operator[](size_t i) const
ThisPolynomialMatrix & operator=(ThisPolynomialMatrix &&other) noexcept=default
PolynomialMatrix(std::vector< PolynomialVector< Trait > > mat)
~PolynomialMatrix()=default
void _const_time_unpoison() const
decltype(auto) begin() const
ThisPolynomialVector & operator=(const ThisPolynomialVector &other)=delete
void _const_time_poison() const
~PolynomialVector()=default
Polynomial< Trait, D > & operator[](size_t i)
std::span< const T > coefficients() const
ThisPolynomialVector & reduce()
constexpr Domain domain() const noexcept
ThisPolynomialVector & operator-=(const ThisPolynomialVector &other)
size_t hamming_weight() const noexcept
PolynomialVector(const ThisPolynomialVector &other)=delete
void _const_time_unpoison() const
ThisPolynomialVector & operator=(ThisPolynomialVector &&other) noexcept=default
decltype(auto) begin() const
const Polynomial< Trait, D > & operator[](size_t i) const
ThisPolynomialVector clone() const
PolynomialVector(ThisPolynomialVector &&other) noexcept=default
std::vector< Polynomial< Trait, D > * > polynomials()
constexpr bool ct_validate_value_range(T min, T max) const noexcept
ThisPolynomialVector & conditional_add_q()
PolynomialVector(size_t vecsize)
decltype(auto) end() const
friend class PolynomialVector
std::span< T > coefficients()
ThisPolynomialVector & operator+=(const ThisPolynomialVector &other)
static PolynomialVector< Trait, D > from_domain_cast(PolynomialVector< Trait, OtherD > &&other)
Polynomial(const ThisPolynomial &other)=delete
constexpr bool owns_storage() const
void _const_time_unpoison() const
ThisPolynomial & operator=(ThisPolynomial &&other) noexcept
T operator[](size_t i) const
Polynomial(std::span< T, Trait::N > coeffs)
Polynomial(ThisPolynomial &&other) noexcept
ThisPolynomial & conditional_add_q()
std::span< const T, Trait::N > coefficients() const
ThisPolynomial & operator=(const ThisPolynomial &other)=delete
static Polynomial< Trait, D > from_domain_cast(Polynomial< Trait, OtherD > &&p)
constexpr size_t hamming_weight() const noexcept
decltype(auto) end() const
std::span< T, Trait::N > coefficients()
constexpr size_t size() const
void _const_time_poison() const
constexpr Domain domain() const noexcept
ThisPolynomial & reduce()
ThisPolynomial clone() const
decltype(auto) begin() const
constexpr bool ct_validate_value_range(T min, T max) const noexcept
static constexpr void barrett_reduce(std::span< T, N > poly)
static constexpr T to_montgomery(T a)
static constexpr T F_WITH_MONTY_SQUARED
static constexpr void poly_sub(std::span< T, N > result, std::span< const T, N > lhs, std::span< const T, N > rhs)
next_longer_int_t< T > T2
static constexpr T Q_inverse
static constexpr T MONTY_SQUARED
static constexpr void poly_cadd_q(std::span< T, N > coeffs)
Adds Q if the coefficient is negative.
static constexpr T fqmul(T a, T b)
static constexpr auto zetas
static constexpr void poly_add(std::span< T, N > result, std::span< const T, N > lhs, std::span< const T, N > rhs)
static constexpr T BARRETT_V
static constexpr std::span< U, N > poly_in_polyvec(std::span< U > polyvec, size_t index)
static constexpr size_t polys_in_polyvec(std::span< const T > polyvec)
static constexpr void polyvec_pointwise_acc_montgomery(std::span< T, N > w, std::span< const T > u, std::span< const T > v)
Multiplication and accumulation of 2 polynomial vectors u and v.
static constexpr Mask< T > set()
static constexpr Mask< T > expand_top_bit(T v)
static constexpr Mask< T > is_within_range(T v, T l, T u)
StructureT< Trait, To > domain_cast(StructureT< Trait, From > &&p)
void dot_product(Polynomial< Trait, Domain::NTT > &out, const PolynomialVector< Trait, Domain::NTT > &a, const PolynomialVector< Trait, Domain::NTT > &b)
void montgomery(Polynomial< Trait, D > &p)
Polynomial< Trait, D > montgomery(Polynomial< Trait, D > p)
PolynomialVector< Trait, Domain::NTT > operator*(const PolynomialMatrix< Trait > &mat, const PolynomialVector< Trait, Domain::NTT > &vec)
PolynomialVector< Trait, Domain::Normal > operator+(const PolynomialVector< Trait, Domain::Normal > &a, const PolynomialVector< Trait, Domain::Normal > &b)
Polynomial< Trait, Domain::NTT > ntt(Polynomial< Trait, Domain::Normal > p)
PolynomialVector< Trait, Domain::Normal > operator<<(const PolynomialVector< Trait, Domain::Normal > &pv, size_t shift)
Polynomial< Trait, Domain::Normal > inverse_ntt(Polynomial< Trait, Domain::NTT > p_ntt)
constexpr void unpoison_range(const R &r)
constexpr void poison_range(const R &r)
constexpr void unpoison(const T *p, size_t n)
constexpr void poison(const T *p, size_t n)
consteval T montgomery_R2(T q)
consteval T montgomery_R(T q)
consteval T modular_inverse(T q, T2 m=T2(1)<< sizeof(T) *8)
constexpr void copy_mem(T *out, const T *in, size_t n)
std::conditional_t< sizeof(T)==1, int16_t, std::conditional_t< sizeof(T)==2, int32_t, std::conditional_t< sizeof(T)==4, int64_t, void > > > next_longer_int_t
constexpr void clear_mem(T *ptr, size_t n)