#include <root_modular.hpp>

Static Public Member Functions

template<typename Polynomial > static Polynomial pow_mod (const Polynomial &a, const integer &n, const Polynomial &f)
template<typename Polynomial > static Polynomial degree_one_factorization (const Polynomial &f, const integer &p)
template<typename Polynomial > static void linear_splitting (Polynomial &g, const Polynomial &f, const integer &p)
template<typename Polynomial > static vector< Polynomial > linear_factorization (const Polynomial &f, const integer &p)
template<typename Polynomial > static vector< typename
scalar_type_helper< Polynomial >
::val > roots (const Polynomial &f, const integer &p)

Detailed Description

Definition at line 31 of file root_modular.hpp.

Member Function Documentation

static Polynomial degree_one_factorization	(	const Polynomial &	f,
		const integer &	p
	)		`[inline, static]`

Definition at line 43 of file root_modular.hpp.

References mmx::C, mmx::gcd(), Polynomial, and root_modular_naive::pow_mod().

Referenced by root_modular_naive::roots().

                                                                 {
  // return the product of the linear factors
  Polynomial x (C(1), 1);
  Polynomial g= pow_mod (x, p, f) - x;
  return gcd (g, f);
}

static vector<Polynomial> linear_factorization	(	const Polynomial &	f,
		const integer &	p
	)		`[inline, static]`

Definition at line 71 of file root_modular.hpp.

References mmx::deg(), root_modular_naive::linear_splitting(), and Polynomial.

Referenced by root_modular_naive::roots().

                                                             {
  VERIFY (f != 0, "bug");
  list<Polynomial> todo (f);
  vector<Polynomial> factors= vec<Polynomial> ();
  if (deg (f) <= 0) return factors;
  while (!is_nil (todo)) {
    Polynomial h= car(todo), g; todo= cdr(todo);
    linear_splitting (g, h, p); 
    if ((nat) deg (g) == 1) factors << g;
    else todo= cons (g, todo);
    if (deg (g) != deg (h)) todo= cons (h / g, todo);
  }
  return factors; }

static void linear_splitting	(	Polynomial &	g,
		const Polynomial &	f,
		const integer &	p
	)		`[inline, static]`

Definition at line 51 of file root_modular.hpp.

References mmx::C, mmx::deg(), mmx::gcd(), Polynomial, and root_modular_naive::pow_mod().

Referenced by root_modular_naive::linear_factorization().

                                                                        {
  VERIFY (f != 0, "bug");
  nat n= deg (f); g= f;
  if (n == 1) return;
  Polynomial x (C(1), 1);
  nat counter= 0;
  while (deg (g) <= 0 || (nat) deg (g) == n) {
    vector<C> _a (C (0), n);
    for (nat i= 0; i < n; i++) _a[i]= C(rand ()); // TODO << improve
    Polynomial a (_a), b;
    g= gcd (a, f);
    if (deg (g) > 0) return;
    g= p == 2 ? gcd (a - 1, f)
              : gcd (pow_mod (a, (p-1) / 2, f) - 1, f);
    counter++;
  }
  //mmout << "Number of equal degree splitting failures: " << counter << "\n";
  ASSERT (deg (g) > 0 && (nat) deg (g) < n, "cannot find a linear factor"); }

static Polynomial pow_mod	(	const Polynomial &	a,
		const integer &	n,
		const Polynomial &	f
	)		`[inline, static]`

Definition at line 34 of file root_modular.hpp.

References Modular_polynomial, Modulus_polynomial, and Polynomial.

Referenced by root_modular_naive::degree_one_factorization(), and root_modular_naive::linear_splitting().

                                                                     {
  Modulus_polynomial _f= Modular_polynomial::get_modulus ();
  Modular_polynomial::set_modulus (f);
  Polynomial g= * binpow (Modular_polynomial (a), n);
  Modular_polynomial::set_modulus (_f);
  return g;
}

static vector< typename scalar_type_helper<Polynomial>::val > roots	(	const Polynomial &	f,
		const integer &	p
	)		`[inline, static]`

Definition at line 86 of file root_modular.hpp.

References mmx::C, mmx::deg(), root_modular_naive::degree_one_factorization(), root_modular_naive::linear_factorization(), mmx::N(), and Polynomial.

Referenced by mmx::separable_roots().

                                              {
  if (deg (f) <= 0) {
    return vector<C> ();
  }
  //mmout << f << "\n";
  Polynomial g= degree_one_factorization (f, p);
  //mmout << g << "\n";
  vector<Polynomial> lin_facts= linear_factorization (g, p);
  vector<C> b (C(), N(lin_facts));
  for (nat i= 0; i < N(lin_facts); i++)
    b[i]= - lin_facts[i][0] / lin_facts[i][1];
  return b; }

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

/Users/mourrain/Devel/mmx/algebramix/include/algebramix/root_modular.hpp