12#ifndef BOTAN_KYBER_POLYNOMIAL_H_
13#define BOTAN_KYBER_POLYNOMIAL_H_
15#include <botan/internal/kyber_constants.h>
16#include <botan/internal/pqcrystals.h>
18#if defined(BOTAN_HAS_KYBER_AVX2)
19 #include <botan/internal/cpuid.h>
20 #include <botan/internal/kyber_avx2.h>
33 constexpr static T montgomery_reduce_coefficient(
T2 a) {
34 const T u =
static_cast<T>(
static_cast<T>(a) *
Q_inverse);
35 auto t =
static_cast<T2>(u) *
Q;
38 return static_cast<T>(t);
41 constexpr static T barrett_reduce_coefficient(
T a) {
43 return static_cast<T>(a - t);
61 constexpr static void ntt(std::span<T, N> p) {
62#if defined(BOTAN_HAS_KYBER_AVX2)
68 for(
size_t len =
N / 2, i = 0; len >= 2; len /= 2) {
69 for(
size_t start = 0, j = 0; start <
N; start = j + len) {
70 const auto zeta =
zetas[++i];
71 for(j = start; j < start + len; ++j) {
72 const auto t =
fqmul(zeta, p[j + len]);
73 p[j + len] =
static_cast<T>(p[j] - t);
74 p[j] =
static_cast<T>(p[j] + t);
94#if defined(BOTAN_HAS_KYBER_AVX2)
100 for(
size_t len = 2, i = 127; len <=
N / 2; len *= 2) {
101 for(
size_t start = 0, j = 0; start <
N; start = j + len) {
102 const auto zeta =
zetas[i--];
103 for(j = start; j < start + len; ++j) {
105 p[j] = barrett_reduce_coefficient(
static_cast<T>(t + p[j + len]));
106 p[j + len] =
fqmul(zeta,
static_cast<T>(p[j + len] - t));
123 std::span<const T, N> lhs,
124 std::span<const T, N> rhs) {
125#if defined(BOTAN_HAS_KYBER_AVX2)
134 const auto basemul = [](
const auto a,
const auto b,
const T zeta) -> std::tuple<T, T> {
136 static_cast<T>(
fqmul(a[0], b[1]) +
fqmul(a[1], b[0]))};
139 const auto Tq_elem_count = [](
auto p) {
return p.size() / 2; };
141 const auto Tq_elem = [](
auto p,
size_t i) {
142 if constexpr(std::is_const_v<
typename decltype(p)::element_type>) {
143 return std::array<T, 2>{p[2 * i], p[2 * i + 1]};
145 return std::tuple<T&, T&>{p[2 * i], p[2 * i + 1]};
149 for(
size_t i = 0; i < Tq_elem_count(result) / 2; ++i) {
150 const T zeta =
zetas[64 + i];
151 const T nzeta =
static_cast<T>(-zeta);
152 Tq_elem(result, 2 * i) = basemul(Tq_elem(lhs, 2 * i), Tq_elem(rhs, 2 * i), zeta);
153 Tq_elem(result, 2 * i + 1) = basemul(Tq_elem(lhs, 2 * i + 1), Tq_elem(rhs, 2 * i + 1), nzeta);
static bool has(CPUID::Feature feat)
static constexpr void barrett_reduce(std::span< T, N > poly)
static constexpr T F_WITH_MONTY_SQUARED
next_longer_int_t< T > T2
static constexpr T Q_inverse
static constexpr T fqmul(T a, T b)
static constexpr auto zetas
static constexpr T BARRETT_V
static constexpr T inverse_ntt_scale()
static constexpr const std::array< T, N/2 > & zeta_table()
Constants shared with the SIMD kernels.
static constexpr void poly_pointwise_montgomery(std::span< T, N > result, std::span< const T, N > lhs, std::span< const T, N > rhs)
static constexpr void inverse_ntt(std::span< T, N > p)
static constexpr T q_inverse()
static constexpr void ntt(std::span< T, N > p)
BOTAN_FN_ISA_AVX2 void inverse_ntt(std::span< int16_t, 256 > p)
BOTAN_FN_ISA_AVX2 void ntt(std::span< int16_t, 256 > p)
BOTAN_FN_ISA_AVX2 void poly_pointwise_montgomery(std::span< int16_t, 256 > result, std::span< const int16_t, 256 > lhs, std::span< const int16_t, 256 > rhs)