source: comparacioncriptosistemas/reescrituraDeCodigo/finitefield2.H

/*
  Copyright (C) 2015
  Alejandro Mujica (amujica en cenditel.gob.ve)
  José Angel 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 plantilla de clase
  para representar campos finitos con carácterística p = 2. Con el fin de
  definir operaciones aritméticas sobre números pertenecientes al campo y
  obtener sus resultados dentro éste.

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

# ifndef FINITEFIELD2_H
# define FINITEFIELD2_H

# include <cmath>
# include <stdexcept>

# include <finitefield.H>

/**
 *  Plantilla que representa un campo finito con característica @f$p = 2@f$.
 *
 *  @tparam NumberT Tipo numérico que se va a restringir.
 *
 *  @tparam N   Valor constante para la potencia de dos que definirá el tamaño
 *              del campo. Por lo tanto, el tamaño del campo estará definido
 *              por @f$2^N@f$.
 *
 *  @pre NumberT debe ser un tipo de los enteros sin signo de la biblioteca
 *       estándar de C++
 *  @pre 0 <= N <= 64
 *
 *  @see FiniteField FieldNumber
 *
 *  @author Alejandro J. Mujica (amujica en cenditel punto gob punto ve).
 *  @author José Angel Contreras (jancontreras en cenditel punto gob punto ve).
 */
template <typename NumberT, unsigned short N>
class FiniteField2 : public FiniteField<NumberT, 2, N>
{
  static_assert(0 <= N and N <= 64, "N must be a value less than 64");

  static constexpr unsigned short TABLE_SIZE = 65; // Desde 2^0 hasta 2^64

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

  using UnifDistType = std::uniform_int_distribution<NumberT>;

public:
  /// Tipo de número que maneja el campo.
  using NumberType = NumberT;

private:
  NumberType irreducible_polynomial;

  void generate_irreducible_polynomial();

public:
  FiniteField2();

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

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

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

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

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

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

template <typename NumberT, unsigned short N>
void FiniteField2<NumberT, N>::generate_irreducible_polynomial()
{
  irreducible_polynomial |= POWER2_TABLE[0];
  irreducible_polynomial |= POWER2_TABLE[1];
  irreducible_polynomial |= POWER2_TABLE[5];
  irreducible_polynomial |= POWER2_TABLE[6];
  irreducible_polynomial |= POWER2_TABLE[8];
}

template <typename NumberT, unsigned short N> 
FiniteField2<NumberT, N>::FiniteField2()
  : irreducible_polynomial(NumberType(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 NumberT, unsigned short N> NumberT
FiniteField2<NumberT, N>::sum(const NumberType & a, const NumberType & b) const
{
  return (a ^ b);
}

/**
 *  @param a Minuendo.
 *  @param b Sustraendo.
 *  @return resta dentro del campo.
 */
template <typename NumberT, unsigned short N> NumberT
FiniteField2<NumberT, N>::sub(const NumberType & a, const NumberType & b) const
{
  return (a ^ b);
}

/**
 *  @param a Multiplicando.
 *  @param b Multiplicador.
 *  @return producto dentro del campo.
 */
template <typename NumberT, unsigned short N> NumberT
FiniteField2<NumberT, N>::mul(const NumberType & a, const NumberType & b) const
{
  NumberType _a(a);
  NumberType _b(b);
  NumberType ret(0);

  for (unsigned short i = 0; i < N; ++i)
    {
      if (_b & 1) // ¿Es impar?
        ret ^= _a;

      _a <<= 1;

      if (_a >= this->size())
        _a ^= irreducible_polynomial;

      _b >>= 1;
    }
  
  return ret;
}

/**
 *  @param a Dividendo.
 *  @param b Divisor.
 *  @return cociente dentro del campo.
 */
template <typename NumberT, unsigned short N> NumberT
FiniteField2<NumberT, N>::div(const NumberType & _a,
                                  const NumberType & _b) const
{
  NumberType ret = NumberType(0);

  NumberType carry;

  NumberType a(_a);
  NumberType b(_b);

  for (unsigned short i = 0; i < N; ++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 @f$a + op(a) = 0@f$.
 */
template <typename NumberT, unsigned short N> NumberT
FiniteField2<NumberT, N>::op(const NumberType & n) const
{
  return this->size() - n;
}

/**
 *  @param a Número.
 *  @return Inverso numérico dentro del campo.  Tal que @f$a * inv(a) = 1@f$.
 */
template <typename NumberT, unsigned short N> NumberT
FiniteField2<NumberT, N>::inv(const NumberType & n) const
{
  if (n == NumberType(0))
    throw std::logic_error("0 has not numeric inverse");

  NumberType inv = NumberType(0);

  while ((inv * n) % this->size() != NumberType(1))
    ++inv;

  return inv;
}

# endif // FINITEFIELD2_H