Represents the polynomial ring GF(q)[y]/F(y) where F(y) is the modulus polynomial in GF(q)[y] of degree t. More...

#include <cmce_poly.h>

Classes
struct	Big_F_Coefficient
	Represents a non-zero coefficient of the modulus F(y) (which is in GF(q)[y]). More...

Public Member Functions
	Classic_McEliece_Polynomial_Ring (std::vector< Big_F_Coefficient > poly_big_f_coef, CmceGfMod poly_f, size_t t)
	Construct a polynomial ring GF(q)[y]/F(y) by defining the polynomial modulus F(y), the GF(q) modulus f(z) and the degree of F(y).

std::optional< Classic_McEliece_Minimal_Polynomial >	compute_minimal_polynomial (StrongSpan< const CmceIrreducibleBits > seed) const
	Compute the minimal polynomial g of polynomial created from a `seed`.

size_t	degree () const
	The degree of polynomials in this ring (and of F(y)).

Classic_McEliece_Polynomial	multiply (const Classic_McEliece_Polynomial &a, const Classic_McEliece_Polynomial &b) const

CmceGfMod	poly_f () const

Detailed Description

Represents the polynomial ring GF(q)[y]/F(y) where F(y) is the modulus polynomial in GF(q)[y] of degree t.

This class contains a modulus polynomial F(y) and the GF(q) modulus f(z). It is used to create and operate with Classic_McEliece_Polynomials.

Definition at line 104 of file cmce_poly.h.

Constructor & Destructor Documentation

◆ Classic_McEliece_Polynomial_Ring()

Botan::Classic_McEliece_Polynomial_Ring::Classic_McEliece_Polynomial_Ring	(	std::vector< Big_F_Coefficient >	poly_big_f_coef,
		CmceGfMod	poly_f,
		size_t	t )

inline

Construct a polynomial ring GF(q)[y]/F(y) by defining the polynomial modulus F(y), the GF(q) modulus f(z) and the degree of F(y).

F(y) is given by a vector of Big_F_Coefficients, where each one represents a monomial of F(y). However, the highest monomial must not be specified, since it is always 1.

Parameters

poly_big_f_coef	The non-zero coefficients of F(y) in GF(q)[y] WITHOUT the highest monomial.
poly_f	The modulus f(z) of GF(q).
t	The polynomial degree of the ring (and of F(y)).

Definition at line 127 of file cmce_poly.h.

127 :

128 m_position_map(std::move(poly_big_f_coef)), m_t(t), m_poly_f(poly_f) {}

Botan::Classic_McEliece_Polynomial_Ring::poly_f

CmceGfMod poly_f() const

Definition cmce_poly.h:130

Member Function Documentation

◆ compute_minimal_polynomial()

std::optional< Classic_McEliece_Minimal_Polynomial > Botan::Classic_McEliece_Polynomial_Ring::compute_minimal_polynomial ( StrongSpan< const CmceIrreducibleBits > seed ) const

Compute the minimal polynomial g of polynomial created from a seed.

Parameters

seed	over the ring GF(q)[y] according to ISO Section 8.1 Step 3.

Returns: g or std::nullopt if g has not full degree.

Definition at line 72 of file cmce_poly.cpp.

                                                     {
   auto polynomial = create_element_from_bytes(seed);
   std::vector<Classic_McEliece_Polynomial> mat;
 
   mat.push_back(create_element_from_coef(concat<std::vector<CmceGfElem>>(
      std::vector<CmceGfElem>{CmceGfElem(1)}, std::vector<CmceGfElem>(degree() - 1, CmceGfElem(0)))));
 
   mat.push_back(polynomial);
 
   for(size_t j = 2; j <= degree(); ++j) {
      mat.push_back(multiply(mat.at(j - 1), polynomial));
   }
 
   // Gaussian
   for(size_t j = 0; j < degree(); ++j) {
      for(size_t k = j + 1; k < degree(); ++k) {
         auto cond = GF_Mask::is_zero(mat.at(j).coef_at(j));
 
         for(size_t c = j; c < degree() + 1; ++c) {
            mat.at(c).coef_at(j) += cond.if_set_return(mat.at(c).coef_at(k));
         }
      }
 
      const bool is_zero_at_diagonal = mat.at(j).coef_at(j).is_zero();
      CT::unpoison(is_zero_at_diagonal);
      if(is_zero_at_diagonal) {
         // Fail if not systematic. New rejection sampling iteration starts.
         return std::nullopt;
      }
 
      auto inv = mat.at(j).coef_at(j).inv();
 
      for(size_t c = j; c < degree() + 1; ++c) {
         mat.at(c).coef_at(j) *= inv;
      }
 
      for(size_t k = 0; k < degree(); ++k) {
         if(k != j) {
            const auto t = mat.at(j).coef_at(k);
 
            for(size_t c = j; c < degree() + 1; ++c) {
               mat.at(c).coef_at(k) += mat.at(c).coef_at(j) * t;
            }
         }
      }
   }
 
   auto minimal_poly_coeffs = mat.at(degree()).coef();
   // Add coefficient 1 since polynomial is monic
   minimal_poly_coeffs.emplace_back(CmceGfElem(1), poly_f());
 
   return Classic_McEliece_Minimal_Polynomial(std::move(minimal_poly_coeffs));
}

References Botan::concat(), degree(), Botan::GF_Mask::is_zero(), multiply(), poly_f(), and Botan::CT::unpoison().

Referenced by Botan::Classic_McEliece_PrivateKeyInternal::check_key().

◆ degree()

size_t Botan::Classic_McEliece_Polynomial_Ring::degree ( ) const

inline

The degree of polynomials in this ring (and of F(y)).

Definition at line 135 of file cmce_poly.h.

135{ return m_t; }

Referenced by compute_minimal_polynomial().

◆ multiply()

Classic_McEliece_Polynomial Botan::Classic_McEliece_Polynomial_Ring::multiply	(	const Classic_McEliece_Polynomial &	a,
		const Classic_McEliece_Polynomial &	b ) const

Returns: a*b over GF(q)[y]/F(y).

Definition at line 30 of file cmce_poly.cpp.

                                                                                                                   {
   std::vector<Classic_McEliece_GF> prod(m_t * 2 - 1, {CmceGfElem(0), m_poly_f});
 
   for(size_t i = 0; i < m_t; ++i) {
      for(size_t j = 0; j < m_t; ++j) {
         prod.at(i + j) += (a.coef_at(i) * b.coef_at(j));
      }
   }
 
   for(size_t i = (m_t - 1) * 2; i >= m_t; --i) {
      for(auto& [idx, coef] : m_position_map) {
         prod.at(i - m_t + idx) += coef * prod.at(i);
      }
   }
 
   prod.erase(prod.begin() + m_t, prod.end());
 
   return Classic_McEliece_Polynomial(std::move(prod));
}