1 // ========================================================================== 2 // Copyright(c)'1994-2010 by The Givaro group 3 // This file is part of Givaro. 4 // Givaro is governed by the CeCILL-B license under French law 5 // and abiding by the rules of distribution of free software. 6 // see the COPYRIGHT file for more details. 7 // file: gfqkronecker.h 8 // Time-stamp: <12 Apr 10 16:45:02 Jean-Guillaume.Dumas@imag.fr> 9 // date: 2007 10 // version: 11 // author: Jean-Guillaume.Dumas 12 13 /*! @file gfqkronecker.h 14 * @ingroup zpz 15 * @brief Arithmetic on GF(p^k), with dynamic Kronecker substitution. 16 * @pre k(p-1)^2 < word size 17 */ 18 19 #ifndef __GIVARO_gfq_kronecker_H 20 #define __GIVARO_gfq_kronecker_H 21 22 #include "givaro/givzpz.h" 23 #include "givaro/givzpzInt.h" 24 #include "givaro/gfq.h" 25 #include "givaro/givpower.h" 26 #include <limits> 27 #include <vector> 28 #include <deque> 29 30 namespace Givaro { 31 32 //! GFqKronecker 33 template<class TT, class Ints> struct GFqKronecker : public GFqDom<TT> { 34 protected: 35 typedef typename Signed_Trait<TT>::unsigned_type UTT; 36 typedef TT Rep; 37 typedef GFqDom<TT> Father_t; 38 39 public: 40 typedef GFqKronecker<TT,Ints> Self_t; 41 42 typedef Rep Element; 43 typedef Element* Element_ptr ; 44 typedef const Element* ConstElement_ptr; 45 46 47 typedef UTT Residu_t; 48 49 typedef Rep* Array; 50 typedef const Rep* constArray; 51 52 typedef ModularRandIter< Father_t , Rep> RandIter; 53 GFqKroneckerGFqKronecker54 GFqKronecker(): Father_t() {} 55 56 // Extension MUST be a parameter of the constructor GFqKroneckerGFqKronecker57 GFqKronecker( const UTT P, const UTT e) : Father_t(P,e), _degree(e-1),_epmunsq(e*(P-1)*(P-1)) { 58 buildsmalltables(); 59 setShift(std::numeric_limits<UTT>::digits/( (e<<1)-1) ); 60 } 61 getMaxnGFqKronecker62 Ints getMaxn() const { 63 return _sMAXN; 64 } getShiftGFqKronecker65 UTT getShift() const { 66 return _SHIFTS; 67 } getBaseGFqKronecker68 UTT getBase() const { 69 return _sBASE; 70 } 71 72 // Set shifts, returns maxn setShiftGFqKronecker73 Ints setShift(const Ints& i) { 74 _SHIFTS=i; 75 _sBASE = Ints(1); _sBASE <<=_SHIFTS; 76 _sMASK = _sBASE - 1; 77 return _sMAXN = _sBASE / _epmunsq; 78 } 79 80 // Set maxn, returns shifts setMaxnGFqKronecker81 UTT setMaxn(const Ints& n) { 82 _sMAXN = n; 83 Ints m = _sMAXN * _epmunsq; 84 _SHIFTS = 0; 85 for(_sBASE = 1; _sBASE < m; ++_SHIFTS, _sBASE<<=1); 86 _sMASK = _sBASE - 1; 87 return _SHIFTS; 88 } 89 90 ~GFqKroneckerGFqKronecker91 virtual ~GFqKronecker() {}; 92 93 using Father_t::init; 94 using Father_t::convert; 95 convertGFqKronecker96 virtual Ints& convert(Ints& r, const Rep a) const { 97 // First Step 98 // from element to polynomial coefficient binary shifted 99 UTT binpol=_log2bin[a]; 100 // Second step 101 // from a0|a1|...|ad 102 // to 0-0ad | ... | 0-0a1 | 0-0a0 103 r = binpol & _pMASK; // a0 104 for(size_t i=1; i<this->_exponent; ++i) { 105 r <<= _SHIFTS; 106 binpol >>= _pceil; 107 r |= ( binpol & _pMASK); 108 } 109 return r; 110 } 111 112 113 initGFqKronecker114 virtual Rep& init(Rep& a, const Ints r) const { 115 // WARNING: This could be speeded up with a REDQ transform 116 117 // First Step lower part 118 // from rd | ... | r1 | r0 119 // to a0|a1|...|ad 120 // where ai = ri mod p 121 Ints rs=r; 122 UTT binpolLOW = (UTT)( (rs & _sMASK) % this->_characteristic); 123 for(size_t i=1; i<this->_exponent; ++i) { 124 binpolLOW <<= _pceil; 125 rs >>= _SHIFTS; 126 binpolLOW |= (UTT)( (rs & _sMASK) % this->_characteristic); 127 } 128 // First Step upper part 129 rs >>= _SHIFTS; 130 UTT binpolHIGH = (UTT)( (rs & _sMASK) % this->_characteristic); 131 for(size_t i=1; i<this->_degree; ++i) { 132 binpolHIGH <<= _pceil; 133 rs >>= _SHIFTS; 134 binpolHIGH |= (UTT)( (rs & _sMASK) % this->_characteristic); 135 } 136 binpolHIGH <<= _pceil; 137 138 // Second step 139 // transform to element H*X^k+L 140 return this->axpy(a, _bin2log[binpolHIGH], _Xk, _bin2log[binpolLOW]); 141 } 142 143 144 145 146 protected: 147 std::ostream& polywrite(std::ostream& out, const Element& a, const Indeter In= "B") const { 148 static Modular<Integer> Zp(this->_characteristic); 149 static Poly1PadicDom<Modular<Integer> > PAD(Zp ,In); 150 static Poly1PadicDom<Modular<Integer> >::Element pol; 151 Integer r; 152 PAD.radixdirect(pol, this->convert(r, a), this->_exponent); 153 return PAD.write(out, pol); 154 } 155 156 buildsmalltablesGFqKronecker157 void buildsmalltables() { 158 _log2bin.resize(this->_log2pol.size()); 159 _pceil = 1; 160 for(unsigned long ppow = 2; ppow < this->_characteristic; ppow <<= 1,++_pceil) {} 161 _pMASK = (1<<_pceil) - 1; 162 163 Father_t Zp(this->_characteristic,1); 164 typedef Poly1FactorDom< Father_t, Dense > PolDom; 165 PolDom Pdom( Zp ); 166 typedef Poly1PadicDom< Father_t, Dense > PadicDom; 167 PadicDom PAD(Pdom); 168 169 typename std::vector<UTT>::iterator binit = _log2bin.begin(); 170 typename std::vector<UTT>::const_iterator polit = this->_log2pol.begin(); 171 for( ; polit != this->_log2pol.end(); ++polit, ++binit) { 172 173 std::vector<unsigned long> vect; 174 PAD.radixdirect( vect, (unsigned long)(*polit), this->_exponent); 175 176 *binit = vect[0]; 177 for(size_t i =1; i<this->_exponent; ++i) { 178 *binit <<= _pceil; 179 *binit += vect[i]; 180 } 181 } 182 183 _bin2log.resize( 1<<(_pceil*this->_exponent) ); 184 for(size_t i=0; i<_log2bin.size(); ++i) 185 _bin2log[ _log2bin[ i ] ] = i; 186 187 188 // This is X 189 _Xk = this->_pol2log[this->_characteristic]; 190 // polywrite(std::cerr << "Xk: " << _Xk << " rep ", _Xk) << std::endl; 191 // This is X^{e} 192 dom_power(_Xk,_Xk,this->_exponent,*this); 193 // polywrite(std::cerr << "Xk: ", _Xk) << std::endl; 194 } 195 196 197 198 UTT _SHIFTS; 199 Ints _sBASE,_sMASK,_sMAXN; 200 201 UTT _pceil,_pMASK,_degree; 202 Ints _epmunsq; 203 204 std::vector<UTT> _log2bin; 205 std::vector<UTT> _bin2log; 206 207 Element _Xk; 208 }; 209 210 } // namespace Givaro 211 212 #endif // __GIVARO_gfq_kronecker_H 213 /* -*- mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ 214 // vim:sts=4:sw=4:ts=4:et:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s 215