root_modular_naive Struct Reference

#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, root_modular_naive::pow_mod(), and mmx::x.

Referenced by root_modular_naive::roots().

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

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

Definition at line 71 of file root_modular.hpp.

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

Referenced by root_modular_naive::roots().

00071                                                              {
00072   VERIFY (f != 0, "bug");
00073   list<Polynomial> todo (f);
00074   vector<Polynomial> factors= vec<Polynomial> ();
00075   if (deg (f) <= 0) return factors;
00076   while (!is_nil (todo)) {
00077     Polynomial h= car(todo), g; todo= cdr(todo);
00078     linear_splitting (g, h, p); 
00079     if ((nat) deg (g) == 1) factors << g;
00080     else todo= cons (g, todo);
00081     if (deg (g) != deg (h)) todo= cons (h / g, todo);
00082   }
00083   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, root_modular_naive::pow_mod(), and mmx::x.

Referenced by root_modular_naive::linear_factorization().

00051                                                                         {
00052   VERIFY (f != 0, "bug");
00053   nat n= deg (f); g= f;
00054   if (n == 1) return;
00055   Polynomial x (C(1), 1);
00056   nat counter= 0;
00057   while (deg (g) <= 0 || (nat) deg (g) == n) {
00058     vector<C> _a (C (0), n);
00059     for (nat i= 0; i < n; i++) _a[i]= C(rand ()); // TODO << improve
00060     Polynomial a (_a), b;
00061     g= gcd (a, f);
00062     if (deg (g) > 0) return;
00063     g= p == 2 ? gcd (a - 1, f)
00064               : gcd (pow_mod (a, (p-1) / 2, f) - 1, f);
00065     counter++;
00066   }
00067   //mmout << "Number of equal degree splitting failures: " << counter << "\n";
00068   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 binpow(), Modular_polynomial, Modulus_polynomial, and Polynomial.

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

00034                                                                      {
00035   Modulus_polynomial _f= Modular_polynomial::get_modulus ();
00036   Modular_polynomial::set_modulus (f);
00037   Polynomial g= * binpow (Modular_polynomial (a), n);
00038   Modular_polynomial::set_modulus (_f);
00039   return g;
00040 }

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::polynomial_modular_roots(), and mmx::separable_roots().

00086                                               {
00087   if (deg (f) <= 0) {
00088     return vector<C> ();
00089   }
00090   //mmout << f << "\n";
00091   Polynomial g= degree_one_factorization (f, p);
00092   //mmout << g << "\n";
00093   vector<Polynomial> lin_facts= linear_factorization (g, p);
00094   vector<C> b (C(), N(lin_facts));
00095   for (nat i= 0; i < N(lin_facts); i++)
00096     b[i]= - lin_facts[i][0] / lin_facts[i][1];
00097   return b; }

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

include/algebramix/root_modular.hpp