1 #if !defined HAVE_FACTOR_H__ 2 #define HAVE_FACTOR_H__ 3 // This file is part of the FXT library. 4 // Copyright (C) 2010, 2011, 2012, 2013, 2014, 2018, 2019 Joerg Arndt 5 // License: GNU General Public License version 3 or later, 6 // see the file COPYING.txt in the main directory. 7 8 9 #include "mod/mtypes.h" 10 #include "bits/bitsperlong.h" 11 #include "fxtio.h" 12 #include "fxttypes.h" 13 14 15 class factorization 16 // Factorization of a numbers into prime powers. 17 // Factors can be supplied for constructor, 18 // otherwise trial division is used. 19 { 20 21 factorization(const factorization &) = delete; 22 const factorization & operator = (const factorization &) = delete; 23 24 protected: 25 ulong npr_; 26 27 #if BITS_PER_LONG_LONG <= 64 28 umod_t prime_[16]; 29 ulong expon_[16]; 30 umod_t prpow_[16]; 31 #else 32 umod_t prime_[32]; 33 ulong expon_[32]; 34 umod_t prpow_[32]; 35 #endif 36 37 umod_t prod_; 38 39 40 public: 41 static const ulong maxprimes; 42 43 friend class mod; 44 45 public: 46 explicit factorization(); 47 explicit factorization(umod_t n, const umod_t* f=nullptr); 48 ~factorization(); 49 nprimes()50 ulong nprimes() const { return npr_; } prime(ulong i)51 umod_t prime(ulong i) const { return prime_[i]; } exponent(ulong i)52 ulong exponent(ulong i) const { return expon_[i]; } 53 ulong exponent_of(umod_t p) const; // exponent of prime p product()54 umod_t product() const { return prod_; } primepow(ulong i)55 umod_t primepow(ulong i) const { return prpow_[i]; } 56 57 bool make_factorization(umod_t n); 58 bool make_factorization(umod_t n, const umod_t *f); 59 is_factorization_of(umod_t n)60 bool is_factorization_of(umod_t n) const { return ( n == product() ); } 61 62 bool is_prime() const; 63 64 ulong numdiv() const; 65 66 void print(const char *bla, std::ostream &os) const; 67 68 bool check() const; 69 70 void reset(); 71 protected: 72 void sort_by_primes(); 73 }; 74 // ------------------------- 75 76 77 // mod/factor.cc: 78 umod_t get_factor_q(umod_t n, umod_t f); 79 ulong divide_out_factor(umod_t &n, umod_t v); 80 81 //istream& operator >> (istream& is, factorization& h); 82 std::ostream& operator << (std::ostream& os, const factorization& h); 83 84 85 #endif // !defined HAVE_FACTOR_H__ 86