modulus_int_preinverse< m > Struct Template Reference

#include <modular_int.hpp>

Inheritance diagram for modulus_int_preinverse< m >:

List of all members.

Static Public Member Functions

static void encode_mod (C &dest, const C &s, const M &m)
static void decode_mod (C &dest, const C &s, const M &m)
static void div_mod (C &dest, const C &s, const M &m)
static void div_mod (C &dest, const C &s1, const C &s2, const M &m)
static void inv_mod_signed (C &a, const C &p)
static void inv_mod_unsigned (C &a, const C &p)
static bool is_invertible_mod (const C &s, const M &m)
static void inv_mod (C &a, const M &m)
static void inv_mod (C &dest, const C &s, const M &m)
static nat dyn_r (const C &p)
static nat dyn_s (const C &p, nat r)
static nat dyn_t (const C &p, nat r)
static C dyn_q (const C &p, nat r, nat s, nat t)
static void mul_mod (C &dest, const C &src, const M &x)
static void mul_mod (C &dest, const C &src, const M &x, C &carry)
static void mul_mod (C &dest, const C &s1, const C &s2, const M &x)
static void mul_mod (C &dest, const C &s1, const C &s2, const M &x, C &carry)
static void neg_mod (C &dest, const M &m)
static void neg_mod (C &dest, const M &m, C &carry)
static void neg_mod (C &dest, const C &s, const M &m)
static void neg_mod (C &dest, const C &s, const M &m, C &carry)
static void add_mod_without_overflow (C &dest, const C &s, const C &p)
static void add_mod_without_overflow (C &dest, const C &s, const C &p, C &carry)
static void add_mod_with_overflow (C &dest, const C &s, const C &p)
static void add_mod_with_overflow (C &dest, const C &s, const C &p, C &carry)
static void add_mod_core (C &dest, const C &s, const C &p)
static void add_mod_core (C &dest, const C &s, const C &p, C &carry)
static void add_mod (C &dest, const C &s, const M &m)
static void add_mod (C &dest, const C &s, const M &m, C &carry)
static void add_mod (C &dest, const C &s1, const C &s2, const M &m)
static void add_mod (C &dest, const C &s1, const C &s2, const M &m, C &carry)
static void sub_mod_core (C &dest, const C &s, const C &p)
static void sub_mod_core (C &dest, const C &s, const C &p, C &carry)
static void sub_mod (C &dest, const C &s, const M &m)
static void sub_mod (C &dest, const C &s, const M &m, C &carry)
static void sub_mod (C &dest, const C &s1, const C &s2, const M &m)
static void sub_mod (C &dest, const C &s1, const C &s2, const M &m, C &carry)
static void reduce_mod_core (C &dest, const C &p)
static void reduce_mod_core (C &dest, const C &p, C &carry)
static void reduce_mod (C &dest, const M &m)
static void reduce_mod (C &dest, const M &m, C &carry)
static void reduce_mod (C &dest, const C &s, const M &m)
static void reduce_mod (C &dest, const C &s, const M &m, C &carry)
static bool normalize (C &p)

Detailed Description

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

Definition at line 927 of file modular_int.hpp.

Member Function Documentation

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.

00208                                                                     {
00209     dest = s1;
00210     add_mod (dest, s2, m, 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.

00203                                                           {
00204     dest = s1;
00205     add_mod (dest, s2, m); }

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.

00199                                                       {
00200     add_mod_core (dest, s, m.p, carry); }

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

Definition at line 195 of file modular_int.hpp.

00195                                             {
00196     add_mod_core (dest, s, m.p); }

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.

00191                                                            {
00192     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.

00187                                                  {
00188     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,
		C &	carry
	)			`[inline, static, inherited]`

Definition at line 146 of file modular_int.hpp.

00146                                                                     {
00147     VERIFY (carry == 0 || carry == 1, "unexpected large carry");
00148     dest += s + carry;
00149     if (dest < s || dest >= p) { dest -= p; carry= 1; }
00150     else carry= 0; }

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.

00140                                                           {
00141     dest += s;
00142     if (dest < s) { dest -= p; return; }
00143     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.

00134                                                                        {
00135     VERIFY (carry == 0 || carry == 1, "unexpected large carry");
00136     dest += s + carry;
00137     if (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.

00129                                                              {
00130     dest += s;
00131     if (dest >= p) dest -= p; }

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

Definition at line 505 of file modular_int.hpp.

00505                                                {
00506     (void) m;
00507     dest = s; }

static void div_mod	(	C &	dest,
		const C &	s1,
		const C &	s2,
		const M &	m
	)			`[inline, static, inherited]`

Definition at line 485 of file modular_int.hpp.

00485                                                           {
00486     dest = s1;
00487     div_mod (dest, s2, m); }

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

Definition at line 479 of file modular_int.hpp.

00479                                             {
00480     C t = s;
00481     V::inv_mod (t, m);
00482     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 647 of file modular_int.hpp.

References _dynamic_inverse_helper< C, D >::op().

00647                                           {
00648     typedef typename unsigned_of_helper<C>::type uC;
00649     typedef typename unsigned_int_with_double_size_helper<C>::type D;
00650     return _dynamic_inverse_helper<C,D>::op ((uC) p, r, s, t);
00651   }

static nat dyn_r ( const C & p ) [inline, static, inherited]

Definition at line 625 of file modular_int.hpp.

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

00625                      {
00626     typedef typename unsigned_of_helper<C>::type uC;
00627     static const nat m = V::template maximum_size_helper<C>::value;
00628     C abs_p = abs (p);
00629     nat r = bit_size (abs_p);
00630     return (r == 0) ? m : ( (uC) abs_p == (((uC) 1) << (r-1)) ? r-1 : r );
00631   }

static nat dyn_s	(	const C &	p,
		nat	r
	)			`[inline, static, inherited]`

Definition at line 634 of file modular_int.hpp.

References mmx::C.

00634                             {
00635     static const nat m = V::template maximum_size_helper<C>::value;
00636     return m+2 <= 8 * sizeof(C) ? r-2 : r-1;
00637   }

static nat dyn_t	(	const C &	p,
		nat	r
	)			`[inline, static, inherited]`

Definition at line 640 of file modular_int.hpp.

References mmx::C, and n.

00640                             {
00641     static const nat n = 8 * sizeof(C);
00642     static const nat m = V::template maximum_size_helper<C>::value;
00643     return (m+2 <= n) ? r+3 : ((m+1 <= n) ? r+1 : r);
00644   }

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

Definition at line 493 of file modular_int.hpp.

00493                                                {
00494     typedef typename unsigned_of_helper<C>::type uC;
00495     if (sign (s) < 0) {
00496       uC tmp = - ((uC) s);
00497       V::reduce_mod (tmp, m);
00498       dest = (C) (((uC) m.p) - tmp);
00499     }
00500     else
00501       dest = s;
00502       V::reduce_mod (dest, m);
00503   }

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

Definition at line 470 of file modular_int.hpp.

00470                                             {
00471     dest = s;
00472     inv_mod (dest, m); }

static void inv_mod	(	C &	a,
		const M &	m
	)			`[inline, static, inherited]`

Definition at line 463 of file modular_int.hpp.

00463                              {
00464     if (V::template maximum_size_helper<C>::value >= 8*sizeof(C))
00465       inv_mod_unsigned(a, m.p);
00466     else
00467       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.

00402                                     {
00403     typedef typename unsigned_of_helper<C>::type uC;
00404     typedef typename signed_of_helper<C>::type sC;
00405     sC coa0=0, coa1=1, r0=p, r1=a, q, t;        
00406     if ((p == 0) && (r1 != 0)) {
00407       q = (((uC) r0) - ((uC) r1)) / ((uC) r1) + 1;
00408       t = r0 - q * r1;
00409       r0 = r1;
00410       r1 = t;
00411       t = coa1;
00412       coa1 = coa0 - q * coa1;
00413       coa0 = t;
00414     }
00415     while (r1 != 0) {
00416       q = r0 / r1;
00417       t = r0 - q * r1;
00418       r0 = r1;
00419       r1 = t;
00420       t = coa1;
00421       coa1 = coa0 - q * coa1;
00422       coa0 = t;
00423     }
00424     if (r0 != 1)
00425       ERROR ("inv_mod: argument is not invertible");
00426     a = coa0 < 0 ? p+coa0 : coa0;
00427   }

static void inv_mod_unsigned	(	C &	a,
		const C &	p
	)			`[inline, static, inherited]`

Definition at line 430 of file modular_int.hpp.

00430                                       {
00431     C coa0=0, coa1=1, r0=p, r1=a, q, t; 
00432     bool toggle = true;
00433     if ((p == 0) && (r1 != 0)) {
00434       q = (r0-r1) / r1 + 1;
00435       t = r0 - q * r1;
00436       r0 = r1;
00437       r1 = t;
00438       t = coa1;
00439       coa1 = coa0 - q * coa1;
00440       coa0 = t;
00441       toggle = !toggle;
00442     }
00443     while (r1 != 0) {
00444       q = r0 / r1;
00445       t = r0 - q * r1;
00446       r0 = r1;
00447       r1 = t;
00448       t = coa1;
00449       coa1 = coa0 - q * coa1;
00450       coa0 = t;
00451       toggle = !toggle;
00452     }
00453     if (r0 != 1)
00454       ERROR ("inv_mod: argument is not invertible");
00455     a = (toggle && (coa0 != 0)) ? p+coa0 : coa0;
00456   }

static bool is_invertible_mod	(	const C &	s,
		const M &	m
	)			`[inline, static, inherited]`

Definition at line 459 of file modular_int.hpp.

00459                                              {
00460     return abs (gcd (s, m.p)) == 1; }

static void mul_mod	(	C &	dest,
		const C &	s1,
		const C &	s2,
		const M &	x,
		C &	carry
	)			`[inline, static, inherited]`

Definition at line 921 of file modular_int.hpp.

References modulus_mul_int_preinverse< V >::mul_mod().

00921                                                                     {
00922     dest = s1;
00923     mul_mod (dest, s2, x, carry); }

static void mul_mod	(	C &	dest,
		const C &	s1,
		const C &	s2,
		const M &	x
	)			`[inline, static, inherited]`

Definition at line 916 of file modular_int.hpp.

References modulus_mul_int_preinverse< V >::mul_mod().

00916                                                           {
00917     dest = s1;
00918     mul_mod (dest, s2, x); }

static void mul_mod	(	C &	dest,
		const C &	src,
		const M &	x,
		C &	carry
	)			`[inline, static, inherited]`

Definition at line 906 of file modular_int.hpp.

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

00906                                                         {
00907     static const nat m = V::template maximum_size_helper<C>::value;
00908     typedef typename unsigned_of_helper<C>::type uC;
00909     typedef typename unsigned_int_with_double_size_helper<uC>::type uD;
00910     uC tmp = dest, ucarry = carry;
00911     mul_mod_helper<uC,uD,m>::op (tmp, (uC) src, (uC) x.p, ucarry,
00912                                  (uC) x.q, x.r, x.s, x.t);
00913     dest = tmp; carry = ucarry; }

static void mul_mod	(	C &	dest,
		const C &	src,
		const M &	x
	)			`[inline, static, inherited]`

Definition at line 896 of file modular_int.hpp.

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

00896                                               {
00897     static const nat m = V::template maximum_size_helper<C>::value;
00898     typedef typename unsigned_of_helper<C>::type uC;
00899     typedef typename unsigned_int_with_double_size_helper<uC>::type uD;
00900     uC tmp = dest;
00901     mul_mod_helper<uC,uD,m>::op (tmp, (uC) src, (uC) x.p,
00902                                  (uC) x.q, x.r, x.s, x.t);
00903     dest = tmp; }

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.

00123                                                       {
00124     VERIFY (carry == 0 || carry == 1, "unexpected large carry");
00125     if (s != 0 || carry != 0) { dest= m.p - s - carry; carry= 1; }
00126     else dest= 0; }

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

Definition at line 119 of file modular_int.hpp.

00119                                             {
00120     if (s != 0) dest = m.p - s; else dest = s; }

static void neg_mod	(	C &	dest,
		const M &	m,
		C &	carry
	)			`[inline, static, inherited]`

Definition at line 114 of file modular_int.hpp.

00114                                           {
00115     VERIFY (carry == 0 || carry == 1, "unexpected large carry");
00116     if (dest != 0 || carry != 0) { dest= m.p - dest - carry; carry= 1; } }

static void neg_mod	(	C &	dest,
		const M &	m
	)			`[inline, static, inherited]`

Definition at line 110 of file modular_int.hpp.

00110                                 {
00111     if (dest != 0) dest = m.p - dest; }

static bool normalize ( C & p ) [inline, static, inherited]

Definition at line 66 of file modular_int.hpp.

00066                    {
00067     typedef typename unsigned_of_helper<C>::type uC;
00068     static const uC a = MMX_SAFE_LEFT_SHIFT_INT(uC, 1,
00069                          V::template maximum_size_helper<C>::value);
00070     p = abs (p);
00071     if ((uC) p == a || p == 0) { p = a; return true; }
00072     return p <= V::template maximum_value_helper<C>::dyn_value ();
00073   }

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.

00101                                                          {
00102     dest = s;
00103     reduce_mod_core (dest, (C) m.p, carry); }

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

Definition at line 96 of file modular_int.hpp.

00096                                                {
00097     dest = s;
00098     reduce_mod_core (dest, (C) m.p); }

static void reduce_mod	(	C &	dest,
		const M &	m,
		C &	carry
	)			`[inline, static, inherited]`

Definition at line 92 of file modular_int.hpp.

00092                                              {
00093     reduce_mod_core (dest, (C) m.p, carry); }

static void reduce_mod	(	C &	dest,
		const M &	m
	)			`[inline, static, inherited]`

Definition at line 88 of file modular_int.hpp.

00088                                    {
00089     reduce_mod_core (dest, (C) m.p); }

static void reduce_mod_core	(	C &	dest,
		const C &	p,
		C &	carry
	)			`[inline, static, inherited]`

Definition at line 83 of file modular_int.hpp.

00083                                                   {
00084     if (p != 0) { carry= dest / p; dest %= p; }
00085     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.

00079                                         {
00080     if (p != 0) dest %= p; }

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.

00238                                                                     {
00239     dest = s1;
00240     sub_mod (dest, s2, m, carry); }

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.

00233                                                           {
00234     dest = s1;
00235     sub_mod (dest, s2, m); }

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.

00229                                                       {
00230     sub_mod_core (dest, s, m.p, carry); }

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

Definition at line 225 of file modular_int.hpp.

00225                                             {
00226     sub_mod_core (dest, s, m.p); }

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.

00218                                                            {
00219     VERIFY (carry == 0 || carry == 1, "unexpected large carry");
00220     C t = s + carry;
00221     if (t == p || dest < t) { dest += p; carry= 1; } else carry= 0;
00222     dest -= t; }

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.

00213                                                  {
00214     if (dest < s) dest += p;
00215     dest -= s; }

The documentation for this struct was generated from the following file:

include/numerix/modular_int.hpp

modulus_int_preinverse< m > Struct Template Reference

Static Public Member Functions

Detailed Description

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

Member Function Documentation

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