modulus_inv_int_naive< V > Struct Template Reference

#include <modular_int.hpp>

List of all members.

Static Public Member Functions

• template<typename C > static void inv_mod_signed (C &a, const C &p)
• template<typename C > static void inv_mod_unsigned (C &a, const C &p)
• template<typename C , typename M > static bool is_invertible_mod (const C &s, const M &m)
• template<typename C , typename M > static void inv_mod (C &a, const M &m)
• template<typename C , typename M > static void inv_mod (C &dest, const C &s, const M &m)

---

Detailed Description

template<typename V>
struct mmx::modulus_inv_int_naive< V >

Definition at line 399 of file modular_int.hpp.

---

Member Function Documentation

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

Definition at line 470 of file modular_int.hpp.

                                            {
    dest = s;
    inv_mod (dest, m); }

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

Definition at line 463 of file modular_int.hpp.

Referenced by modulus_inv_int_naive< modulus_mul_int_naive< modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< size > > > > > >::inv_mod().

                             {
    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]

Definition at line 402 of file modular_int.hpp.

Referenced by modulus_inv_int_naive< modulus_mul_int_naive< modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< size > > > > > >::inv_mod().

                                    {
    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]

Definition at line 430 of file modular_int.hpp.

Referenced by modulus_inv_int_naive< modulus_mul_int_naive< modulus_add_int_naive< modulus_reduction_int_naive< modulus_normalization_int_naive< modulus_maximum_size_int< size > > > > > >::inv_mod().

                                      {
    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 bool is_invertible_mod	(	const C &	s,
		const M &	m
	)			[inline, static]

Definition at line 459 of file modular_int.hpp.

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

---

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

• include/numerix/modular_int.hpp