/usr/include/givaro/givpoly1factor.h is in libgivaro-dev 4.0.2-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 | // ================================================================= //
// Copyright(c)'1994-2009 by The Givaro group
// This file is part of Givaro.
// Givaro is governed by the CeCILL-B license under French law
// and abiding by the rules of distribution of free software.
// see the COPYRIGHT file for more details.
// Time-stamp: <23 Oct 15 15:35:46 Jean-Guillaume.Dumas@imag.fr>
// ================================================================= //
/** @file givpoly1factor.h
* @ingroup poly1
* @brief NO DOC
* - Irreducibily test
* - Factorisations de Polynomes dans Fp[X] :
* - Distinct Degree
* - Cantor-Zassenhaus
* - Berlekamp: moved in LinBox
* .
*/
#ifndef __GIVARO_poly1_facto_H
#define __GIVARO_poly1_facto_H
#include <givaro/givrandom.h>
#include <givaro/givpoly1.h>
namespace Givaro {
// template<class Domain, class StorageTag> class Poly1FactorDom {};
//! Poly1FactorDom
template<class Domain, class Tag = Dense, class RandomIterator = GivRandom>
class Poly1FactorDom : public Poly1Dom<Domain,Tag> {
protected:
using Poly1Dom<Domain,Tag>::_domain;
typedef typename Poly1Dom<Domain,Tag>::Rep Rep;
mutable RandomIterator _g;
public:
using Poly1Dom<Domain,Tag>::one;
using Poly1Dom<Domain,Tag>::zero;
typedef typename Poly1Dom<Domain,Tag>::Element Element;
typedef RandomIterator random_generator;
typedef typename Domain::Residu_t Residu_t;
typedef typename Signed_Trait<typename Domain::Element>::signed_type Element_t;
// using typename Poly1Dom<Domain,Tag>::Type_t; //used for assign (clang complains)
typedef typename Poly1Dom<Domain,Tag>::Type_t Type_t; //used for assign (clang complains)
// typedef typename Domain::Residu_t Residu_t;
Poly1FactorDom () {}
//! @warning there is a copy of the random Iterator ...
Poly1FactorDom (Domain& d, const Indeter& X = Indeter(), const RandomIterator& g = RandomIterator() ) :
Poly1Dom<Domain,Tag> (d,X), _g(g)
{}
Poly1FactorDom (const Poly1Dom<Domain,Tag>& P, const RandomIterator& g = RandomIterator()) :
Poly1Dom<Domain,Tag> (P), _g(g)
{}
// ---------------------------------------------------------------
// Splits a polynomial into prime factors of same degree
// ---------------------------------------------------------------
template< template<class, class> class Container, template<class> class Alloc >
void SplitFactor( Container< Rep, Alloc<Rep> > & L
, const Rep& G
, Degree d
, Residu_t MOD) const ;
template< template<class, class> class Container, template <class> class Alloc>
void SplitFactor( Container< Rep, Alloc<Rep> > & L
, const Rep& G
, Degree d) const {
SplitFactor(L,G,d,_domain.residu());
}
Rep& SplitFactor(
Rep& R
, const Rep& G
, Degree d
, Residu_t MOD) const ;
Rep& SplitFactor(
Rep& R
, const Rep& G
, Degree d) const {
return SplitFactor(R,G,d,_domain.residu() );
}
// ---------------------------------------------------------------
// Splits a polynomial into divisors of homogenous prime factors
// ---------------------------------------------------------------
template< template<class, class> class Container, template<class> class Alloc>
void DistinctDegreeFactor(Container< Rep, Alloc<Rep> > & L
, const Rep& f
, Residu_t MOD) const ;
template< template<class, class> class Container, template <class> class Alloc>
void DistinctDegreeFactor( Container< Rep, Alloc<Rep> > & L
, const Rep& f) const {
DistinctDegreeFactor(L,f,_domain.residu());
}
// ---------------------------------------------------------------
// Cantor-Zassenhaus Polynomial factorization over Z/pZ
// ---------------------------------------------------------------
template< template<class, class> class Container, template <class> class Alloc>
void CZfactor( Container< Rep, Alloc<Rep> > & Lf,
Container< uint64_t, Alloc<uint64_t> > & Le,
const Rep& f,
Residu_t MOD) const ;
template< template<class, class> class Container, template <class> class Alloc>
void CZfactor( Container< Rep, Alloc<Rep> > & Lf,
Container< uint64_t, Alloc<uint64_t> > & Le,
const Rep& f ) const {
CZfactor(Lf, Le, f,_domain.residu());
}
// ---------------------------------------------------------------
// Gives one non-trivial factor of P if P is reducible
// returns P otherwise
// ---------------------------------------------------------------
Rep& factor(
Rep& W
, const Rep& P
, Residu_t MOD ) const ;
Rep& factor(
Rep& W
, const Rep& P ) const {
return factor(W,P,_domain.residu());
}
template<class PolyCont>
PolyCont& factor (PolyCont& factors,
std::vector<uint64_t>& exp,
const Rep& P) {
// JGD 02.03.2012 : to be refactored
// at least without pointers ...
CZfactor(factors, exp, P); // Cantor-Zassenhaus factorization
return factors;
}
// ---------------------------------------------------------------
// Irreducibility test
// ---------------------------------------------------------------
bool is_irreducible( const Rep& P
, Residu_t MOD ) const ;
bool is_irreducible( const Rep& P ) const
{
return is_irreducible(P,_domain.residu());
}
bool is_irreducible2( const Rep& P
, Residu_t MOD ) const ;
bool is_irreducible2( const Rep& P ) const
{
return is_irreducible2(P,_domain.residu());
}
// ---------------------------------------------------------------
// Irreducible polynomials
// ---------------------------------------------------------------
/// random irreducible polynomial
Element& random_irreducible (Element& P, Degree n) const ;
/// random irreducible polynomial tries to be sparse
Element& creux_random_irreducible (Element& P, Degree n) const ;
/// random irreducible polynomial with X as primitive root
Element& ixe_irreducible (Element& R, Degree n) const ;
/// random irreducible polynomial with X as primitive root
Element& ixe_irreducible2 (Element& R, Degree n) const ;
// ---------------------------------------------------------------
// Primitive polynomials
// ---------------------------------------------------------------
IntegerDom::Element order(const Rep& P, const Rep& F) const ;
bool is_prim_root( const Rep& P, const Rep& F) const ;
Rep& random_prim_root(Rep& P, Rep& R, Degree n) const ;
Rep& give_random_prim_root(Rep& R, const Rep& F) const ;
Rep& give_prim_root(Rep& R, const Rep& F) const ;
private :
template<class Residue>
bool find_irred_binomial(Element &R, Degree n, Residue MOD) const;
bool find_irred_binomial(Element &R, Degree n, bool MOD) const;
template<class Residue>
bool find_irred_binomial(Element &R, Degree n, Residue MOD, Element IXE) const;
bool find_irred_binomial(Element &R, Degree n, bool MOD, Element IXE) const;
template<class Residue>
bool find_irred_binomial2(Element &R, Degree n, Residue MOD, Element IXE) const;
bool find_irred_binomial2(Element &R, Degree n, bool MOD, Element IXE) const;
template<class Residue>
bool find_irred_trinomial(Element &R, Degree n, Residue MOD) const;
bool find_irred_trinomial(Element &R, Degree n, bool MOD) const;
template<class Residue>
bool find_irred_trinomial(Element &R, Degree n, Residue MOD, Element IXE) const;
bool find_irred_trinomial(Element &R, Degree n, bool MOD, Element IXE) const;
template<class Residue>
bool find_irred_trinomial2(Element &R, Degree n, Residue MOD, Element IXE) const;
bool find_irred_trinomial2(Element &R, Degree n, bool MOD, Element IXE) const;
template<class Residue>
bool find_irred_randomial(Element &R, Degree n, Residue MOD) const;
bool find_irred_randomial(Element &R, Degree n, bool MOD) const;
template<class Residue>
bool find_irred_randomial(Element &R, Degree n, Residue MOD, Element IXE) const;
bool find_irred_randomial(Element &R, Degree n, bool MOD, Element IXE) const;
template<class Residue>
bool find_irred_randomial2(Element &R, Degree n, Residue MOD, Element IXE) const;
bool find_irred_randomial2(Element &R, Degree n, bool MOD, Element IXE) const;
};
} // Givaro
#include "givaro/givpoly1factor.inl"
#include "givaro/givpoly1proot.inl"
#endif // __GIVARO_poly1_facto_H
/* -*- mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
// vim:sts=8:sw=8:ts=8:noet:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s
|