source: comparacioncriptosistemas/binary_field.H @ 1b57940

/*
  Copyright (C) 2015
  Alejandro Mujica (amujica en cenditel.gob.ve)
  José Ángel Contreras (jancontreras en cenditel.gob.ve)
  Antonio Araujo (aaraujo en cenditel.gob.ve)
  Pedro Buitrago (pbuitrago en cenditel.gob.ve)
 
  CENDITEL Fundación Centro Nacional de Desarrollo e Investigación en
  Tecnologías Libres
 
  Este programa es software libre; Usted puede usarlo bajo los términos de la
  licencia de software GPL versión 2.0 de la Free Software Foundation.
 
  Este programa se distribuye con la esperanza de que sea útil, pero SIN
  NINGUNA GARANTÍA; tampoco las implícitas garantías de MERCANTILIDAD o
  ADECUACIÓN A UN PROPÓSITO PARTICULAR.
  Consulte la licencia GPL para más detalles. Usted debe recibir una copia
  de la GPL junto con este programa; si no, escriba a la Free Software
  Foundation Inc. 51 Franklin Street,5 Piso, Boston, MA 02110-1301, USA.
*/

/*
  Este archivo contiene la definición e implementación de una clase tipo
  plantilla para representar campos finitos binarios. Con el fin de definir
  operaciones aritméticas sobre números pertenecientes al campo y obtener
  sus resultados dentro del campo.

  Creado por:        Alejandro J. Mujica
  Fecha de creación: 
*/

# ifndef BINARY_FIELD_H
# define BINARY_FIELD_H

# include <cmath>
# include <random>
# include <stdexcept>

/**
 *  Plantilla que representa un campo finito binario.
 *
 *  @param Number_Type Tipo numérico que se va a restringir. Debe ser un tipo
 *                     de los enteros de la biblioteca estándar de C++.
 *
 *  @param K   Valor constante que representa el máximo número del
 *                     campo.
 *
 *  @author Alejandro J. Mujica (amujica en cenditel punto gob punto ve).
 *  @author José Angel Contreras (jancontreras en cenditel punto gob punto ve).
 */
template <typename Number_Type, uint8_t K>
class Binary_Field
{
  static_assert(std::is_integral<Number_Type>::value,
                "template argument is not an integral type");

  typedef std::uniform_int_distribution<Number_Type> unif_dist_t;

  static constexpr uint8_t P = 2;

  static constexpr Number_Type MAX_VALUE = std::pow(P, K);

  static constexpr Number_Type LAST_BIT = std::pow(2, K - 1);

  static constexpr uint8_t TABLE_SIZE = 64;

  static constexpr uint64_t BIT_TABLE[] =
    {
       1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192,
       16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304,
       8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912,
       1073741824, 2147483648, 4294967296, 8589934592, 17179869184,
       34359738368, 68719476736, 137438953472, 274877906944, 549755813888,
       1099511627776, 2199023255552, 4398046511104, 8796093022208,
       17592186044416, 35184372088832, 70368744177664, 140737488355328,
       281474976710656, 562949953421312, 1125899906842624, 2251799813685248,
       4503599627370496, 9007199254740992, 18014398509481984,
       36028797018963968, 72057594037927936, 144115188075855872,
       288230376151711744, 576460752303423488, 1152921504606846976,
       2305843009213693952, 4611686018427387904, 9223372036854775808,
       9223372036854775808
    };

  number_t irreducible_polynomial;

  void generate_irreducible_polynomial();

public:
  Field();

  /// Tipo de número que maneja el campo.
  typedef Number_Type number_t;

  /// Retorna el máximo valor soportado por el campo.
  number_t max_value() const
  {
    return MAX_VALUE;
  }

  /// Efectúa la suma de dos números dentro del campo.
  number_t sum(const number_t &, const number_t &) const;

  /// Efectúa la resta de dos números dentro del campo.
  number_t sub(const number_t &, const number_t &) const;

  /// Efectúa la multiplicación de dos números dentro del campo.
  number_t mul(const number_t &, const number_t &) const;

  /// Efectúa la división de dos números dentro del campo.
  number_t div(const number_t &, const number_t &) const;

  /// Calcula el opuesto de un número dentro del campo.
  number_t op(const number_t &) const;

  /// Calcula el inverso numérico de un número dentro del campo.
  number_t inv(const number_t &) const;

  /// Genera un número aleatorio dentro del campo.
  template <class Random_Number_Generator>
  number_t get_random(Random_Number_Generator &) const;

  number_t operator () (const number_t & n)
  {
    return n % MAX_VALUE;
  }
};

template <typename Number_Type, uint8_t K>
void Binary_Field<Number_Type, K>::generate_irreducible_polynomial()
{
  irreducible_polynomial |= std::pow(2, 0);
  irreducible_polynomial |= std::pow(2, 1);
  irreducible_polynomial |= std::pow(2, 5);
  irreducible_polynomial |= std::pow(2, 6);
  irreducible_polynomial |= std::pow(2, 8);
}

template <typename Number_Type, uint8_t K> 
Binary_Field<Number_Type, K>::Binary_Field()
  : irreducible_polynomial(number_t(0))
{
  generate_irreducible_polynomial();
}

/**
 *  @param a Primer elemento en la suma.
 *  @param b Segundo elemento en la suma.
 *  @return suma dentro del campo.
 */
template <typename Number_Type, uint8_t K> Number_Type
Binary_Field<Number_Type, K>::sum(const number_t & a, const number_t & b) const
{
  return (a ^ b) % MAX_VALUE;
}

/**
 *  @param a Minuendo.
 *  @param b Sustraendo.
 *  @return resta dentro del campo.
 */
template <typename Number_Type, uint8_t K> Number_Type
Binary_Field<Number_Type, K>::sub(const number_t & a, const number_t & b) const
{
  return (a + op(b)) % MAX_VALUE;
}

/**
 *  @param a Multiplicando.
 *  @param b Multiplicador.
 *  @return producto dentro del campo.
 */
template <typename Number_Type, uint8_t K> Number_Type
Binary_Field<Number_Type, K>::mul(const number_t & a, const number_t & b) const
{
  return (a * b) % MAX_VALUE;
}

/**
 *  @param a Dividendo.
 *  @param b Divisor.
 *  @return cociente dentro del campo.
 */
template <typename Number_Type, uint8_t K> Number_Type
Binary_Field<Number_Type, K>::div(const number_t & _a,
                                  const number_t & _b) const
{
  number_t ret = number_t(0);

  number_t carry;

  number_t a(_a);
  number_t b(_b);

  for (uint8_t i = 0; i < K; ++i)
    {
      if (b & 1)
        ret ^= a;

      carry = a & LAST_BIT;

      a <<= 1;

      if (carry)
        a ^= irreducible_polynomial;

      b >>= 1;
    }

  return ret;
}

/**
 *  @param a Número.
 *  @return Opuesto numérico dentro del campo. Tal que a + (-a) = 0.
 */
template <typename Number_Type, uint8_t K> Number_Type
Binary_Field<Number_Type, K>::op(const number_t & n) const
{
  return MAX_VALUE - n;
}

/**
 *  @param a Número.
 *  @return Inverso numérico dentro del campo.  Tal que a * a^(-1) = 1.
 */
template <typename Number_Type, uint8_t K> Number_Type
Binary_Field<Number_Type, K>::inv(const number_t & n) const
{
  if (n == number_t(0))
    throw std::logic_error("0 has not numeric inverse");

  number_t inv = number_t(0);

  while ((inv * n) % MAX_VALUE != number_t(1))
    ++inv;

  return inv;
}

/**
 *  @param rng Generador de números aleatorios. Éste debe ser uno de los
 *             generadores de la biblioteca estándar de C++.
 *  @return Número aleatorio dentro del campo uniformemente distribuido.
 */
template <typename Number_Type, uint8_t K>
template <class Random_Number_Generator> Number_Type
Binary_Field<Number_Type, K>::get_random(Random_Number_Generator & rng) const
{
  unif_dist_t unif_dist(0, MAX_VALUE);

  return unif_dist(rng);
}

# endif // BINARY_FIELD_H