/usr/include/givaro/givpoly1factor.h is in libgivaro-dev 3.2.13-1.2.
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 | // ================================================================= //
// Givaro / Athapascan-1
// Irreducibily test
// Factorisations de Polynomes dans Fp[X] :
// Distinct Degree
// Cantor-Zassenhaus
// Berlekamp : in LinBox
// Time-stamp: <27 Jun 05 11:35:32 Jean-Guillaume.Dumas@imag.fr>
// ================================================================= //
#ifndef _GIV_POLY1_FACTO_H_
#define _GIV_POLY1_FACTO_H_
#include <givaro/givrandom.h>
#include <givaro/givpoly1.h>
// template<class Domain, class StorageTag> class Poly1FactorDom {};
template<class Domain, class Tag, class RandIter = GivRandom>
class Poly1FactorDom : public Poly1Dom<Domain,Tag> {
protected:
using Poly1Dom<Domain,Tag>::_domain;
using Poly1Dom<Domain,Tag>::one;
using Poly1Dom<Domain,Tag>::zero;
typedef typename Poly1Dom<Domain,Tag>::Rep Rep;
mutable RandIter _g;
public:
typedef typename Poly1Dom<Domain,Tag>::Element Element;
typedef RandIter random_generator;
// typedef typename Domain::Residu_t Residu_t;
typedef typename Signed_Trait<typename Domain::Element>::unsigned_type Residu_t;
// Warning : there is a copy of the random Iterator ...
Poly1FactorDom (Domain& d, const Indeter& X = Indeter(), const RandIter& g = RandIter() ) : Poly1Dom<Domain,Tag> (d,X), _g(g) {}
Poly1FactorDom (const Poly1Dom<Domain,Tag>& P, const RandIter& g = RandIter()) : 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< unsigned long, Alloc<unsigned long> > & 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< unsigned long, Alloc<unsigned long> > & 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());
}
// ---------------------------------------------------------------
// 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 ;
};
#include "givaro/givpoly1factor.inl"
#include "givaro/givpoly1proot.inl"
#endif
|