src/kronecker_modular_int.cpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : kronecker_modular_int.cpp
* DESCRIPTION: Kronecker substitution for hardware modular integers
* COPYRIGHT  : (C) 2009  Gregoire Lecerf
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#include <algebramix/kronecker_int.hpp>
#include <algebramix/kronecker_modular_int.hpp>
namespace mmx {

/******************************************************************************
* Naive encoding and decoding of integer polynomials using Kronecker's method
******************************************************************************/

#if !defined(__GNU_MP__)

template<typename I> inline void
decode_kronecker_mod_int (I* dest, nat n, xnat bits, const integer& src,
                          const I& p) {
  if (n == 0);
  else if (n == 1) dest[0]= as<I> (p == 0 ? src : src % p);
  else {
    nat h= n>>1;
    integer aux= src >> (h*bits);
    decode_kronecker_mod_int (dest+h, n-h, bits, aux, p);
    aux= src - (aux << (h*bits));
    decode_kronecker_mod_int (dest, h, bits, aux, p);
  }
}

#define IMPLEMENTATION_HELPER(I)                                        \
  void                                                                  \
  decode_kronecker_mod (I* dest, nat n, xnat bits, const integer& src,  \
                        const I& p) {                                   \
    decode_kronecker_mod_int (dest, n, bits, src, p); }
IMPLEMENTATION_HELPER (signed char)
IMPLEMENTATION_HELPER (unsigned char)
IMPLEMENTATION_HELPER (short int)
IMPLEMENTATION_HELPER (unsigned short int)
IMPLEMENTATION_HELPER (int)
IMPLEMENTATION_HELPER (unsigned int)
IMPLEMENTATION_HELPER (long int)
IMPLEMENTATION_HELPER (unsigned long int)
IMPLEMENTATION_HELPER (long long int)
IMPLEMENTATION_HELPER (unsigned long long int)
#undef IMPLEMENTATION_HELPER

#else

/******************************************************************************
* Specific implementation for GMP
******************************************************************************/

// from polynomial_gmp.cpp
#define DECLARE_HELPER(I)                                               \
  void mpz_decode_kronecker_mod (I* dest, unsigned long n,              \
                                 unsigned long bits, const mpz_t src,   \
                                 const I& p);
DECLARE_HELPER(unsigned char)
DECLARE_HELPER(unsigned short)
DECLARE_HELPER(unsigned int)
DECLARE_HELPER(unsigned long int)
DECLARE_HELPER(unsigned long long int)
#undef DECLARE_HELPER

#define IMPLEMENTATION_HELPER(I)                                        \
  inline void                                                           \
  decode_kronecker_mod (I* dest, nat n, xnat bits,                      \
                                    const integer& src,                 \
                                    const I& p) {                       \
    typedef unsigned_of_helper<I>::type U;                              \
    mpz_decode_kronecker_mod ((U*) (void*) dest, (unsigned long) n,     \
                              (unsigned long) bits, *src, (U) p); }
IMPLEMENTATION_HELPER(signed char)
IMPLEMENTATION_HELPER(unsigned char)
IMPLEMENTATION_HELPER(short int)
IMPLEMENTATION_HELPER(unsigned short)
IMPLEMENTATION_HELPER(int)
IMPLEMENTATION_HELPER(unsigned int)
IMPLEMENTATION_HELPER(long int)
IMPLEMENTATION_HELPER(unsigned long int)
IMPLEMENTATION_HELPER(long long int)
IMPLEMENTATION_HELPER(unsigned long long int)
#undef IMPLEMENTATION_HELPER

#endif // __GNU_MP__

/******************************************************************************
* Multiply two integer polynomials stored in segments using Kronecker's method
******************************************************************************/

template<typename I> static inline void
mul_kronecker_mod_int (I* dest,
                       const I* src1, nat n1,
                       const I* src2, nat n2, const I& p)
{
  if (n1 == 0 && n2 == 0) return;
  for (nat i= 0; i < n1 + n2 - 1; i++) dest[i]= 0;
  while (n1 > 0 && src1[n1-1] == 0) n1--;
  while (n2 > 0 && src2[n2-1] == 0) n2--;
  if (n1 == 0 || n2 == 0) return;

  xnat bits= 2 * bit_size (p-1) + bit_size (min (n1, n2));
  integer aux1, aux2;
  encode_kronecker (aux1, src1, n1, bits);
  encode_kronecker (aux2, src2, n2, bits);
  integer aux= aux1*aux2;
  decode_kronecker_mod (dest, n1+n2-1, bits, aux, p);
}

#define IMPLEMENTATION_HELPER(I)                                        \
  void mul_kronecker_mod (I* dest, const I* src1, nat n1,               \
                          const I* src2, nat n2, const I& p) {          \
    mul_kronecker_mod_int (dest, src1, n1, src2, n2, p); }
IMPLEMENTATION_HELPER (signed char)
IMPLEMENTATION_HELPER (unsigned char)
IMPLEMENTATION_HELPER (short int)
IMPLEMENTATION_HELPER (unsigned short int)
IMPLEMENTATION_HELPER (int)
IMPLEMENTATION_HELPER (unsigned int)
IMPLEMENTATION_HELPER (long int)
IMPLEMENTATION_HELPER (unsigned long int)
IMPLEMENTATION_HELPER (long long int)
IMPLEMENTATION_HELPER (unsigned long long int)
#undef IMPLEMENTATION_HELPER

template<typename I> static inline void
square_kronecker_mod_int (I* dest, const I* src, nat n, const I& p) {
  if (n == 0) return;
  for (nat i= 0; i < 2 * n - 1; i++) dest[i]= 0;
  while (n > 0 && src[n-1] == 0) n--;
  if (n == 0) return;
  if (n == 1) { dest[0]= square (src[0]); return; }

  xnat bits= 2 * bit_size (p-1) + bit_size (n);
  integer aux1;
  encode_kronecker (aux1, src, n, bits);
  integer aux= square (aux1);
  decode_kronecker_mod (dest, 2*n - 1, bits, aux, p);
}

#define IMPLEMENTATION_HELPER(I)                                         \
  void square_kronecker_mod (I* dest, const I* src, nat n, const I& p) { \
    square_kronecker_mod_int (dest, src, n, p); }
IMPLEMENTATION_HELPER (signed char)
IMPLEMENTATION_HELPER (unsigned char)
IMPLEMENTATION_HELPER (short int)
IMPLEMENTATION_HELPER (unsigned short int)
IMPLEMENTATION_HELPER (int)
IMPLEMENTATION_HELPER (unsigned int)
IMPLEMENTATION_HELPER (long int)
IMPLEMENTATION_HELPER (unsigned long int)
IMPLEMENTATION_HELPER (long long int)
IMPLEMENTATION_HELPER (unsigned long long int)
#undef IMPLEMENTATION_HELPER

} // namespace mmx

---