1 // -*- mode:C++ -*- 2 /* 3 * Copyright (C) 2000,2014 B. Parisse, Institut Fourier, 38402 St Martin d'Heres 4 * 5 * This program is free software; you can redistribute it and/or modify 6 * it under the terms of the GNU General Public License as published by 7 * the Free Software Foundation; either version 3 of the License, or 8 * (at your option) any later version. 9 * 10 * This program is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 * GNU General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License 16 * along with this program. If not, see <http://www.gnu.org/licenses/>. 17 */ 18 19 #ifndef _GIAC_MODFACTOR_H_ 20 #define _GIAC_MODFACTOR_H_ 21 #include "first.h" 22 #include "global.h" 23 24 #ifndef NO_NAMESPACE_GIAC 25 namespace giac { 26 #endif // ndef NO_NAMESPACE_GIAC 27 template<class T> class tensor; 28 typedef tensor<gen> polynome; 29 typedef vecteur modpoly; 30 typedef vecteur dense_POLY1; // same internal rep but assumes non modular op 31 32 // ************************************************************** 33 // factorization utilities 34 // to be used to factor a square-free unitary mod polynomial 35 // assuming modulo is prime (and not too large, must fit in int) 36 // ************************************************************* 37 void intersect(std::vector<bool>::iterator tab, std::vector<bool>::iterator othertab,int size) ; 38 int sigma(const std::vector<bool> & deg); 39 40 // v[i]=x^(p*i) mod q 41 // matrix of the v[i] for i=0..jstart or i=0..degree(q) if jstart=0 42 void qmatrix(const modpoly & q,environment * env,std::vector<modpoly> & v,int jstart=0); 43 // compute s(x)=r(x^p) mod q using the q-matrix 44 void xtoxpowerp(const modpoly & r, const std::vector<modpoly> & v,environment * env,int qsize,modpoly & s); 45 // find modular roots and linear factors 46 bool roots(const modpoly & q, environment * env,vecteur & v,std::vector<modpoly> & w); 47 // Find linear factors of q in Z or Z[i] depending on env->complexe 48 int do_linearfind(const polynome & q,environment * env,polynome & qrem,vectpoly & v,vecteur & croots,int & i); 49 // find linear factor if NTL not installed 50 int linearfind(const polynome & q,environment * env,polynome & qrem,vectpoly & v,int &ithprime); 51 // distinct degree modular factorization 52 bool ddf(const modpoly & q,const std::vector<modpoly> & qmat,environment *env,std::vector< facteur<modpoly> >& v); 53 // split a polynomial ddfactor into factors of same degree i 54 bool cantor_zassenhaus(const modpoly & ddfactor,int i,const std::vector<modpoly> & qmat, environment * env,std::vector<modpoly> & v); 55 bool cantor_zassenhaus(const std::vector< facteur<modpoly> > & v_in,const std::vector<modpoly> & qmat, environment * env,std::vector<modpoly> & v); 56 // number of factors of a ddf factorization 57 int nfact(const std::vector< facteur<modpoly> > & v,bool * possible_degrees , int maxdeg); 58 59 // Landau-Mignotte bound 60 gen mignotte_bound(const dense_POLY1 & p); 61 gen mignotte_bound(const polynome & p); 62 63 // lift factorization from Z/pZ to Z/p^kZ for a sufficiently large k 64 // modulo is modified to modulo^k 65 bool liftl(environment * env,dense_POLY1 & q,gen &bound,std::vector<modpoly> & v_in,vectpoly & v_out); 66 // given a factorization v_in of q in Z/p^kZ find a factorization v_out 67 // over Z, k is the minimal # of factors of v_in to be combined 68 void combine(const dense_POLY1 & q, const std::vector<modpoly> & v_in,environment * env,vectpoly & v_out,std::vector<bool> & possible_degrees, int k=1); 69 70 bool do_factorunivsqff(const polynome & q,environment * env,vectpoly & v,int & i,int debug,int modfactor_primes); 71 bool factorunivsqff(const polynome & q,environment * env,vectpoly & v,int & ithprime,int debug,int modfactor_primes); 72 73 #ifndef NO_NAMESPACE_GIAC 74 } // namespace giac 75 #endif // NO_NAMESPACE_GIAC 76 77 #endif // _GIAC_MODFACTOR_H 78