My Project
fac_util.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 
4 #include "config.h"
5 
6 
7 #include "cf_assert.h"
8 
9 #include "cf_defs.h"
10 #include "canonicalform.h"
11 #include "cf_iter.h"
12 #include "fac_util.h"
13 #include "cfUnivarGcd.h"
14 
16 
17 static CanonicalForm mappk ( const CanonicalForm& );
18 
20 
21 
23 {
24  p = 0;
25  k = 0;
26  pk = 1;
27  pkhalf = 0;
28 }
29 
30 modpk::modpk( int q, int l )
31 {
32  p = q;
33  k = l;
34  pk = power( CanonicalForm( p ), k );
35  pkhalf = pk / 2;
36 }
37 
38 modpk::modpk( const modpk & m )
39 {
40  p = m.p;
41  k = m.k;
42  pk = m.pk;
43  pkhalf = m.pkhalf;
44 }
45 
46 modpk&
48 {
49  if ( this != &m ) {
50  p = m.p;
51  k = m.k;
52  pk = m.pk;
53  pkhalf = m.pkhalf;
54  }
55  return *this;
56 }
57 
59 modpk::inverse( const CanonicalForm & f, bool symmetric ) const
60 {
61  CanonicalForm u, r0 = this->operator()( f, false ), r1 = pk, q0 = 1, q1 = 0;
62  while ( ( r0 > 0 ) && ( r1 > 0 ) ) {
63  u = r0 / r1;
64  r0 = r0 % r1;
65  q0 = u*q1 + q0;
66  if ( r0 > 0 ) {
67  u = r1 / r0;
68  r1 = r1 % r0;
69  q1 = u*q0 + q1;
70  }
71  }
72  if ( r0 == 0 )
73  return this->operator()( pk-q1, symmetric );
74  else
75  return this->operator()( q0, symmetric );
76 }
77 
79 modpk::operator() ( const CanonicalForm & f, bool symmetric ) const
80 {
81  PKHALF = pkhalf;
82  PK = pk;
83  if ( symmetric )
84  return mapdomain( f, mappksymmetric );
85  else
86  return mapdomain( f, mappk );
87 }
88 
90 replaceLc( const CanonicalForm & f, const CanonicalForm & c )
91 {
92  if ( f.inCoeffDomain() )
93  return c;
94  else
95  return f + ( c - LC( f ) ) * power( f.mvar(), degree( f ) );
96 }
97 
100 {
101  CanonicalForm result = mod( f, PK );
102  if ( result > PKHALF )
103  return result - PK;
104  else
105  return result;
106 }
107 
109 mappk ( const CanonicalForm & f )
110 {
111  return mod( f, PK );
112 }
113 
115 remainder( const CanonicalForm & f, const CanonicalForm & g, const modpk & pk )
116 {
117  ASSERT( (f.inCoeffDomain() || f.isUnivariate()) && (g.inCoeffDomain() || g.isUnivariate()) && (f.inCoeffDomain() || g.inCoeffDomain() || f.mvar() == g.mvar()), "can not build remainder" );
118  if ( f.inCoeffDomain() )
119  if ( g.inCoeffDomain() )
120  return pk( f % g );
121  else
122  return pk( f );
123  else {
124  Variable x = f.mvar();
126  int degg = g.degree();
127  CanonicalForm invlcg = pk.inverse( g.lc() );
128  CanonicalForm gg = pk( g*invlcg );
129  if((gg.lc().isOne()))
130  {
131  while ( result.degree() >= degg )
132  {
133  result -= pk(lc( result ) * gg) * power( x, result.degree() - degg );
134  result=pk(result);
135  }
136  }
137  else
138  // no inverse found
139  {
141  if (!ic.isOne())
142  {
143  gg=g/ic;
144  return remainder(f,gg,pk);
145  }
146  while ( result.degree() >= degg )
147  {
148  if (gg.lc().isZero()) return result;
149  CanonicalForm lcgf = result.lc() / gg.lc();
150  if (lcgf.inZ())
151  gg = pk( g*lcgf );
152  else
153  {
154  //printf("!\n\n");
155  return result;
156  }
157  result -= gg * power( x, result.degree() - degg );
158  result=pk(result);
159  }
160  }
161  return result;
162  }
163 }
164 
166 prod ( const CFArray & a, int f, int l )
167 {
168  if ( f < a.min() ) f = a.min();
169  if ( l > a.max() ) l = a.max();
170  CanonicalForm p = 1;
171  for ( int i = f; i <= l; i++ )
172  p *= a[i];
173  return p;
174 }
175 
177 prod ( const CFArray & a )
178 {
179  return prod( a, a.min(), a.max() );
180 }
181 
182 void
183 extgcd ( const CanonicalForm & a, const CanonicalForm & b, CanonicalForm & S, CanonicalForm & T, const modpk & pk )
184 {
185  int p = pk.getp(), k = pk.getk(), j;
186  CanonicalForm amodp, bmodp, smodp, tmodp, s, t, sigma, tau, e;
187  CanonicalForm modulus = p, sigmat, taut, q;
188 
189  setCharacteristic( p );
190  {
191  amodp = mapinto( a ); bmodp = mapinto( b );
192  (void)extgcd( amodp, bmodp, smodp, tmodp );
193  }
194  setCharacteristic( 0 );
195  s = mapinto( smodp ); t = mapinto( tmodp );
196 
197  for ( j = 1; j < k; j++ ) {
198  e = ( 1 - s * a - t * b ) / modulus;
199  setCharacteristic( p );
200  {
201  e = mapinto( e );
202  sigmat = smodp * e;
203  taut = tmodp * e;
204  divrem( sigmat, bmodp, q, sigma );
205  tau = taut + q * amodp;
206  }
207  setCharacteristic( 0 );
208  s += mapinto( sigma ) * modulus;
209  t += mapinto( tau ) * modulus;
210  modulus *= p;
211  }
212  S = s; T = t;
213 }
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
CanonicalForm mapinto(const CanonicalForm &f)
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
CanonicalForm lc(const CanonicalForm &f)
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
CanonicalForm mapdomain(const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )
Definition: cf_ops.cc:440
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4084
int p
Definition: cfModGcd.cc:4080
g
Definition: cfModGcd.cc:4092
CanonicalForm b
Definition: cfModGcd.cc:4105
void tau(int **points, int sizePoints, int k)
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
factory switches.
Iterators for CanonicalForm's.
FILE * f
Definition: checklibs.c:9
int max() const
Definition: ftmpl_array.cc:104
int min() const
Definition: ftmpl_array.cc:98
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isZero() const
CF_NO_INLINE bool isOne() const
bool inZ() const
predicates
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
factory's class for variables
Definition: factory.h:134
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
CanonicalForm operator()(const CanonicalForm &f, bool symmetric=true) const
Definition: fac_util.cc:79
modpk & operator=(const modpk &m)
Definition: fac_util.cc:47
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
Definition: fac_util.cc:59
int getk() const
Definition: fac_util.h:36
modpk()
Definition: fac_util.cc:22
int getp() const
Definition: fac_util.h:35
int p
Definition: fac_util.h:27
CanonicalForm pkhalf
Definition: fac_util.h:26
CanonicalForm pk
Definition: fac_util.h:25
int k
Definition: fac_util.h:28
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int s
Definition: facAbsFact.cc:51
int degg
Definition: facAlgExt.cc:64
int j
Definition: facHensel.cc:110
static CanonicalForm mappksymmetric(const CanonicalForm &)
Definition: fac_util.cc:99
void extgcd(const CanonicalForm &a, const CanonicalForm &b, CanonicalForm &S, CanonicalForm &T, const modpk &pk)
Definition: fac_util.cc:183
STATIC_INST_VAR CanonicalForm PKHALF
Definition: fac_util.cc:15
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
Definition: fac_util.cc:115
CanonicalForm prod(const CFArray &a, int f, int l)
Definition: fac_util.cc:166
STATIC_INST_VAR CanonicalForm PK
Definition: fac_util.cc:15
static CanonicalForm mappk(const CanonicalForm &)
Definition: fac_util.cc:109
CanonicalForm replaceLc(const CanonicalForm &f, const CanonicalForm &c)
Definition: fac_util.cc:90
operations mod p^k and some other useful functions for factorization
#define STATIC_INST_VAR
Definition: globaldefs.h:10
STATIC_VAR jList * T
Definition: janet.cc:30