numerix_doc 0.4
Static Public Member Functions
modulus_int_preinverse< m > Struct Template Reference

#include <modular_int.hpp>

Inheritance diagram for modulus_int_preinverse< m >:
modulus_encoding_int_naive< modulus_div_int_naive< modulus_inv_int_naive< modulus_mul_int_preinverse< modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< m > > > > > > > > modulus_div_int_naive< modulus_inv_int_naive< modulus_mul_int_preinverse< modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< m > > > > > > > modulus_inv_int_naive< modulus_mul_int_preinverse< modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< m > > > > > > modulus_mul_int_preinverse< modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< m > > > > > modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< m > > > > modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< m > > > modulus_normalization_int_naive< modulus_maximum_size_int< m > > modulus_maximum_size_int< m >

List of all members.

Static Public Member Functions

Detailed Description

template<nat m>
struct mmx::modulus_int_preinverse< m >

Examples:

modular_test.cpp.

Definition at line 923 of file modular_int.hpp.

Member Function Documentation

static void add_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 195 of file modular_int.hpp.

                                            {
    add_mod_core (dest, s, m.p); }
static void add_mod ( C &  dest,
const C &  s,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 199 of file modular_int.hpp.

                                                      {
    add_mod_core (dest, s, m.p, carry); }
static void add_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m 
) [inline, static, inherited]

Definition at line 203 of file modular_int.hpp.

                                                          {
    dest = s1;
    add_mod (dest, s2, m); }
static void add_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 208 of file modular_int.hpp.

                                                                    {
    dest = s1;
    add_mod (dest, s2, m, carry); }
static void add_mod_core ( C &  dest,
const C &  s,
const C &  p,
C &  carry 
) [inline, static, inherited]

Definition at line 191 of file modular_int.hpp.

                                                           {
    add_mod_helper<C,is_signed_helper<C>::value>::op (dest, s, p, carry); }
static void add_mod_core ( C &  dest,
const C &  s,
const C &  p 
) [inline, static, inherited]

Definition at line 187 of file modular_int.hpp.

                                                 {
    add_mod_helper<C,is_signed_helper<C>::value>::op (dest, s, p); }
static void add_mod_with_overflow ( C &  dest,
const C &  s,
const C &  p 
) [inline, static, inherited]

Definition at line 140 of file modular_int.hpp.

                                                          {
    dest += s;
    if (dest < s) { dest -= p; return; }
    if (dest >= p) dest -= p; }
static void add_mod_with_overflow ( C &  dest,
const C &  s,
const C &  p,
C &  carry 
) [inline, static, inherited]

Definition at line 146 of file modular_int.hpp.

                                                                    {
    VERIFY (carry == 0 || carry == 1, "unexpected large carry");
    dest += s + carry;
    if (dest < s || dest >= p) { dest -= p; carry= 1; }
    else carry= 0; }
static void add_mod_without_overflow ( C &  dest,
const C &  s,
const C &  p 
) [inline, static, inherited]

Definition at line 129 of file modular_int.hpp.

                                                             {
    dest += s;
    if (dest >= p) dest -= p; }
static void add_mod_without_overflow ( C &  dest,
const C &  s,
const C &  p,
C &  carry 
) [inline, static, inherited]

Definition at line 134 of file modular_int.hpp.

                                                                       {
    VERIFY (carry == 0 || carry == 1, "unexpected large carry");
    dest += s + carry;
    if (dest >= p) { dest -= p; carry= 1; } else carry= 0; }
static void decode_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 501 of file modular_int.hpp.

                                               {
    (void) m;
    dest = s; }
static void div_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m 
) [inline, static, inherited]

Definition at line 481 of file modular_int.hpp.

                                                          {
    dest = s1;
    div_mod (dest, s2, m); }
static void div_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 475 of file modular_int.hpp.

                                            {
    C t = s;
    V::inv_mod (t, m);
    V::mul_mod (dest, t, m); }
static C dyn_q ( const C &  p,
nat  r,
nat  s,
nat  t 
) [inline, static, inherited]

Definition at line 643 of file modular_int.hpp.

References mmx::D, and modulus_mul_int_preinverse< V >::_dynamic_inverse_helper< C, D >::op().

                                          {
    typedef typename unsigned_of_helper<C>::type uC;
    typedef typename unsigned_int_with_double_size_helper<C>::type D;
    return _dynamic_inverse_helper<C,D>::op ((uC) p, r, s, t);
  }
static nat dyn_r ( const C &  p) [inline, static, inherited]

Definition at line 621 of file modular_int.hpp.

References mmx::abs(), and mmx::C.

                     {
    typedef typename unsigned_of_helper<C>::type uC;
    static const nat m = V::template maximum_size_helper<C>::value;
    C abs_p = abs (p);
    nat r = bit_size (abs_p);
    return (r == 0) ? m : ( (uC) abs_p == (((uC) 1) << (r-1)) ? r-1 : r );
  }
static nat dyn_s ( const C &  p,
nat  r 
) [inline, static, inherited]

Definition at line 630 of file modular_int.hpp.

References mmx::C.

                            {
    static const nat m = V::template maximum_size_helper<C>::value;
    return m+2 <= 8 * sizeof(C) ? r-2 : r-1;
  }
static nat dyn_t ( const C &  p,
nat  r 
) [inline, static, inherited]

Definition at line 636 of file modular_int.hpp.

References mmx::C.

                            {
    static const nat n = 8 * sizeof(C);
    static const nat m = V::template maximum_size_helper<C>::value;
    return (m+2 <= n) ? r+3 : ((m+1 <= n) ? r+1 : r);
  }
static void encode_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 489 of file modular_int.hpp.

                                               {
    typedef typename unsigned_of_helper<C>::type uC;
    if (sign (s) < 0) {
      uC tmp = - ((uC) s);
      V::reduce_mod (tmp, m);
      dest = (C) (((uC) m.p) - tmp);
    }
    else
      dest = s;
      V::reduce_mod (dest, m);
  }
static void inv_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 466 of file modular_int.hpp.

                                            {
    dest = s;
    inv_mod (dest, m); }
static void inv_mod ( C &  a,
const M &  m 
) [inline, static, inherited]

Definition at line 459 of file modular_int.hpp.

                             {
    if (V::template maximum_size_helper<C>::value >= 8*sizeof(C))
      inv_mod_unsigned(a, m.p);
    else
      inv_mod_signed(a, m.p); }
static void inv_mod_signed ( C &  a,
const C &  p 
) [inline, static, inherited]

Definition at line 402 of file modular_int.hpp.

                                    {
    typedef typename unsigned_of_helper<C>::type uC;
    typedef typename signed_of_helper<C>::type sC;
    sC coa0=0, coa1=1, r0=p, r1=a, q, t;        
    if ((p == 0) && (r1 != 0)) {
      q = (((uC) r0) - ((uC) r1)) / ((uC) r1) + 1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
      t = coa1;
      coa1 = coa0 - q * coa1;
      coa0 = t;
    }
    while (r1 != 0) {
      q = r0 / r1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
      t = coa1;
      coa1 = coa0 - q * coa1;
      coa0 = t;
    }
    if (r0 != 1)
      ERROR ("inv_mod: argument is not invertible");
    a = coa0 < 0 ? p+coa0 : coa0;
  }
static void inv_mod_unsigned ( C &  a,
const C &  p 
) [inline, static, inherited]

Definition at line 430 of file modular_int.hpp.

                                      {
    C coa0=0, coa1=1, r0=p, r1=a, q, t; 
    bool toggle = true;
    if ((p == 0) && (r1 != 0)) {
      q = (r0-r1) / r1 + 1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
      t = coa1;
      coa1 = coa0 - q * coa1;
      coa0 = t;
      toggle = !toggle;
    }
    while (r1 != 0) {
      q = r0 / r1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
      t = coa1;
      coa1 = coa0 - q * coa1;
      coa0 = t;
      toggle = !toggle;
    }
    if (r0 != 1)
      ERROR ("inv_mod: argument is not invertible");
    a = (toggle && (coa0 != 0)) ? p+coa0 : coa0;
  }
static void mul_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  x,
C &  carry 
) [inline, static, inherited]

Definition at line 917 of file modular_int.hpp.

References modulus_mul_int_preinverse< V >::mul_mod().

                                                                    {
    dest = s1;
    mul_mod (dest, s2, x, carry); }
static void mul_mod ( C &  dest,
const C &  src,
const M &  x 
) [inline, static, inherited]

Definition at line 892 of file modular_int.hpp.

References modulus_mul_int_preinverse< V >::mul_mod_helper< C, D, m >::op().

                                              {
    static const nat m = V::template maximum_size_helper<C>::value;
    typedef typename unsigned_of_helper<C>::type uC;
    typedef typename unsigned_int_with_double_size_helper<uC>::type uD;
    uC tmp = dest;
    mul_mod_helper<uC,uD,m>::op (tmp, (uC) src, (uC) x.p,
                                 (uC) x.q, x.r, x.s, x.t);
    dest = tmp; }
static void mul_mod ( C &  dest,
const C &  src,
const M &  x,
C &  carry 
) [inline, static, inherited]

Definition at line 902 of file modular_int.hpp.

References modulus_mul_int_preinverse< V >::mul_mod_helper< C, D, m >::op().

                                                        {
    static const nat m = V::template maximum_size_helper<C>::value;
    typedef typename unsigned_of_helper<C>::type uC;
    typedef typename unsigned_int_with_double_size_helper<uC>::type uD;
    uC tmp = dest, ucarry = carry;
    mul_mod_helper<uC,uD,m>::op (tmp, (uC) src, (uC) x.p, ucarry,
                                 (uC) x.q, x.r, x.s, x.t);
    dest = tmp; carry = ucarry; }
static void mul_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  x 
) [inline, static, inherited]

Definition at line 912 of file modular_int.hpp.

References modulus_mul_int_preinverse< V >::mul_mod().

                                                          {
    dest = s1;
    mul_mod (dest, s2, x); }
static void neg_mod ( C &  dest,
const M &  m 
) [inline, static, inherited]

Definition at line 110 of file modular_int.hpp.

                                {
    if (dest != 0) dest = m.p - dest; }
static void neg_mod ( C &  dest,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 114 of file modular_int.hpp.

                                          {
    VERIFY (carry == 0 || carry == 1, "unexpected large carry");
    if (dest != 0 || carry != 0) { dest= m.p - dest - carry; carry= 1; } }
static void neg_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 119 of file modular_int.hpp.

                                            {
    if (s != 0) dest = m.p - s; else dest = s; }
static void neg_mod ( C &  dest,
const C &  s,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 123 of file modular_int.hpp.

                                                      {
    VERIFY (carry == 0 || carry == 1, "unexpected large carry");
    if (s != 0 || carry != 0) { dest= m.p - s - carry; carry= 1; }
    else dest= 0; }
static bool normalize ( C &  p) [inline, static, inherited]

Definition at line 66 of file modular_int.hpp.

                   {
    typedef typename unsigned_of_helper<C>::type uC;
    static const uC a = MMX_SAFE_LEFT_SHIFT_INT(uC, 1,
                         V::template maximum_size_helper<C>::value);
    p = abs (p);
    if ((uC) p == a || p == 0) { p = a; return true; }
    return p <= V::template maximum_value_helper<C>::dyn_value ();
  }
static void reduce_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 96 of file modular_int.hpp.

                                               {
    dest = s;
    reduce_mod_core (dest, (C) m.p); }
static void reduce_mod ( C &  dest,
const M &  m 
) [inline, static, inherited]

Definition at line 88 of file modular_int.hpp.

                                   {
    reduce_mod_core (dest, (C) m.p); }
static void reduce_mod ( C &  dest,
const C &  s,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 101 of file modular_int.hpp.

                                                         {
    dest = s;
    reduce_mod_core (dest, (C) m.p, carry); }
static void reduce_mod ( C &  dest,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 92 of file modular_int.hpp.

                                             {
    reduce_mod_core (dest, (C) m.p, carry); }
static void reduce_mod_core ( C &  dest,
const C &  p,
C &  carry 
) [inline, static, inherited]

Definition at line 83 of file modular_int.hpp.

                                                  {
    if (p != 0) { carry= dest / p; dest %= p; }
    else carry = 0; }
static void reduce_mod_core ( C &  dest,
const C &  p 
) [inline, static, inherited]

Definition at line 79 of file modular_int.hpp.

                                        {
    if (p != 0) dest %= p; }
static void sub_mod ( C &  dest,
const C &  s,
const M &  m 
) [inline, static, inherited]

Definition at line 225 of file modular_int.hpp.

                                            {
    sub_mod_core (dest, s, m.p); }
static void sub_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m 
) [inline, static, inherited]

Definition at line 233 of file modular_int.hpp.

                                                          {
    dest = s1;
    sub_mod (dest, s2, m); }
static void sub_mod ( C &  dest,
const C &  s1,
const C &  s2,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 238 of file modular_int.hpp.

                                                                    {
    dest = s1;
    sub_mod (dest, s2, m, carry); }
static void sub_mod ( C &  dest,
const C &  s,
const M &  m,
C &  carry 
) [inline, static, inherited]

Definition at line 229 of file modular_int.hpp.

                                                      {
    sub_mod_core (dest, s, m.p, carry); }
static void sub_mod_core ( C &  dest,
const C &  s,
const C &  p 
) [inline, static, inherited]

Definition at line 213 of file modular_int.hpp.

                                                 {
    if (dest < s) dest += p;
    dest -= s; }
static void sub_mod_core ( C &  dest,
const C &  s,
const C &  p,
C &  carry 
) [inline, static, inherited]

Definition at line 218 of file modular_int.hpp.

                                                           {
    VERIFY (carry == 0 || carry == 1, "unexpected large carry");
    C t = s + carry;
    if (t == p || dest < t) { dest += p; carry= 1; } else carry= 0;
    dest -= t; }
The documentation for this struct was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Friends Defines