Macros | Functions | Variables
gfops.h File Reference

Operations in GF, where GF is a finite field of size less than 2^16 represented by a root of Conway polynomial. More...

#include <iostream>
#include "cf_assert.h"
#include "cf_defs.h"
#include "canonicalform.h"

Go to the source code of this file.

Macros

#define OSTREAM   std::ostream
 

Functions

bool gf_iszero (int a)
 
bool gf_iszero (long a)
 
bool gf_isone (int a)
 
bool gf_isone (long a)
 
int gf_int2gf (int i)
 
long gf_int2gf (long i)
 
int gf_zero ()
 
int gf_one ()
 
int gf_sign (int a)
 
int gf_neg (int a)
 
int gf_add (int a, int b)
 
int gf_sub (int a, int b)
 
int gf_mul (int a, int b)
 
long gf_mul (long a, int b)
 
int gf_div (int a, int b)
 
int gf_inv (int a)
 
void gf_print (OSTREAM &os, int a)
 
int gf_power (int a, int n)
 
long gf_power (long a, int n)
 
void gf_setcharacteristic (int p, int n, char name)
 
long gf_gf2ff (long a)
 
int gf_gf2ff (int a)
 
bool gf_isff (long a)
 
bool gf_isff (int a)
 

Variables

int gf_q
 
int gf_p
 
int gf_n
 
int gf_q1
 
int gf_m1
 
char gf_name
 
unsigned short * gf_table
 
CanonicalForm gf_mipo
 

Detailed Description

Operations in GF, where GF is a finite field of size less than 2^16 represented by a root of Conway polynomial.

Uses look up tables for addition.

See also
gf_tabutil.h

Definition in file gfops.h.

Macro Definition Documentation

#define OSTREAM   std::ostream

Definition at line 19 of file gfops.h.

Function Documentation

int gf_add ( int  a,
int  b 
)
inline

Definition at line 133 of file gfops.h.

134 {
135  // z^a+z^b=z^b*(z^(a-b)+1), if a>=b;
136  // =z^a*(z^(b-a)+1), if a<b;
137  if ( a == gf_q ) return b;
138  if ( b == gf_q ) return a;
139  int zb, zab, r;
140  if ( a >= b ) {
141  zb = b;
142  zab = a - b;
143  }
144  else {
145  zb = a;
146  zab = b - a;
147  }
148  if ( gf_table[zab] == gf_q )
149  r = gf_q; /*if z^(a-b)+1 =0*/
150  else {
151  r= zb + gf_table[zab];
152  if ( r >= gf_q1 )
153  r -= gf_q1;
154  }
155  return r;
156 }
const poly a
Definition: syzextra.cc:212
int gf_q1
Definition: gfops.cc:50
int gf_q
Definition: gfops.cc:47
unsigned short * gf_table
Definition: gfops.cc:54
const ring r
Definition: syzextra.cc:208
const poly b
Definition: syzextra.cc:213
int gf_div ( int  a,
int  b 
)
inline

Definition at line 185 of file gfops.h.

186 {
187  ASSERT( b != gf_q, "divide by zero" );
188  if ( a == gf_q )
189  return gf_q;
190  else {
191  int s = a - b;
192  if (s < 0)
193  s += gf_q1;
194  return s;
195  }
196 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
const poly a
Definition: syzextra.cc:212
int gf_q1
Definition: gfops.cc:50
int gf_q
Definition: gfops.cc:47
#define ASSERT(expression, message)
Definition: cf_assert.h:99
const poly b
Definition: syzextra.cc:213
long gf_gf2ff ( long  a)

Definition at line 226 of file gfops.cc.

227 {
228  if ( gf_iszero( a ) )
229  return 0;
230  else
231  {
232  // starting from z^0=1, step through the table
233  // counting the steps until we hit z^a or z^0
234  // again. since we are working in char(p), the
235  // latter is guaranteed to be fulfilled.
236  long i = 0, ff = 1;
237  do
238  {
239  if ( i == a )
240  return ff;
241  ff++;
242  i = gf_table[i];
243  } while ( i != 0 );
244  return -1;
245  }
246 }
unsigned short * gf_table
Definition: gfops.cc:54
const poly a
Definition: syzextra.cc:212
bool gf_iszero(int a)
Definition: gfops.h:43
int i
Definition: cfEzgcd.cc:123
int gf_gf2ff ( int  a)

Definition at line 248 of file gfops.cc.

249 {
250  if ( gf_iszero( a ) )
251  return 0;
252  else
253  {
254  // starting from z^0=1, step through the table
255  // counting the steps until we hit z^a or z^0
256  // again. since we are working in char(p), the
257  // latter is guaranteed to be fulfilled.
258  int i = 0, ff = 1;
259  do
260  {
261  if ( i == a )
262  return ff;
263  ff++;
264  i = gf_table[i];
265  } while ( i != 0 );
266  return -1;
267  }
268 }
unsigned short * gf_table
Definition: gfops.cc:54
const poly a
Definition: syzextra.cc:212
bool gf_iszero(int a)
Definition: gfops.h:43
int i
Definition: cfEzgcd.cc:123
int gf_int2gf ( int  i)
inline

Definition at line 65 of file gfops.h.

66 {
67  while ( i < 0 )
68  i += gf_p;
69  while ( i >= gf_p )
70  i -= gf_p;
71  if ( i == 0 )
72  return gf_q;
73  int c = 0;
74  while ( i > 1 ) {
75  c = gf_table[c];
76  i--;
77  }
78  return c;
79 }
int gf_p
Definition: gfops.cc:48
int gf_q
Definition: gfops.cc:47
unsigned short * gf_table
Definition: gfops.cc:54
int i
Definition: cfEzgcd.cc:123
long gf_int2gf ( long  i)
inline

Definition at line 81 of file gfops.h.

82 {
83  while ( i < 0 )
84  i += gf_p;
85  while ( i >= gf_p )
86  i -= gf_p;
87  if ( i == 0 )
88  return gf_q;
89  long c = 0;
90  while ( i > 1 ) {
91  c = gf_table[c];
92  i--;
93  }
94  return c;
95 }
int gf_p
Definition: gfops.cc:48
int gf_q
Definition: gfops.cc:47
unsigned short * gf_table
Definition: gfops.cc:54
int i
Definition: cfEzgcd.cc:123
int gf_inv ( int  a)
inline

Definition at line 198 of file gfops.h.

199 {
200  ASSERT( a != gf_q, "divide by zero" );
201  return gf_q1 - a;
202 }
const poly a
Definition: syzextra.cc:212
int gf_q1
Definition: gfops.cc:50
int gf_q
Definition: gfops.cc:47
#define ASSERT(expression, message)
Definition: cf_assert.h:99
bool gf_isff ( long  a)

Definition at line 270 of file gfops.cc.

271 {
272  if ( gf_iszero( a ) )
273  return true;
274  else
275  {
276  // z^a in GF(p) iff (z^a)^p-1=1
277  return gf_isone( gf_power( a, gf_p - 1 ) );
278  }
279 }
const poly a
Definition: syzextra.cc:212
bool gf_isone(int a)
Definition: gfops.h:53
bool gf_iszero(int a)
Definition: gfops.h:43
int gf_p
Definition: gfops.cc:48
int gf_power(int a, int n)
Definition: gfops.h:222
bool gf_isff ( int  a)

Definition at line 281 of file gfops.cc.

282 {
283  if ( gf_iszero( a ) )
284  return true;
285  else
286  {
287  // z^a in GF(p) iff (z^a)^p-1=1
288  return gf_isone( gf_power( a, gf_p - 1 ) );
289  }
290 }
const poly a
Definition: syzextra.cc:212
bool gf_isone(int a)
Definition: gfops.h:53
bool gf_iszero(int a)
Definition: gfops.h:43
int gf_p
Definition: gfops.cc:48
int gf_power(int a, int n)
Definition: gfops.h:222
bool gf_isone ( int  a)
inline

Definition at line 53 of file gfops.h.

54 {
55  return 0 == a;
56 }
const poly a
Definition: syzextra.cc:212
bool gf_isone ( long  a)
inline

Definition at line 58 of file gfops.h.

59 {
60  return 0 == a;
61 }
const poly a
Definition: syzextra.cc:212
bool gf_iszero ( int  a)
inline

Definition at line 43 of file gfops.h.

44 {
45  return gf_q == a;
46 }
const poly a
Definition: syzextra.cc:212
int gf_q
Definition: gfops.cc:47
bool gf_iszero ( long  a)
inline

Definition at line 48 of file gfops.h.

49 {
50  return gf_q == a;
51 }
const poly a
Definition: syzextra.cc:212
int gf_q
Definition: gfops.cc:47
int gf_mul ( int  a,
int  b 
)
inline

Definition at line 163 of file gfops.h.

164 {
165  if ( a == gf_q || b == gf_q )
166  return gf_q;
167  else {
168  int i = a + b;
169  if ( i >= gf_q1 ) i -= gf_q1;
170  return i;
171  }
172 }
const poly a
Definition: syzextra.cc:212
int gf_q1
Definition: gfops.cc:50
int gf_q
Definition: gfops.cc:47
int i
Definition: cfEzgcd.cc:123
const poly b
Definition: syzextra.cc:213
long gf_mul ( long  a,
int  b 
)
inline

Definition at line 174 of file gfops.h.

175 {
176  if ( a == gf_q || b == gf_q )
177  return gf_q;
178  else {
179  long i = a + b;
180  if ( i >= gf_q1 ) i -= gf_q1;
181  return i;
182  }
183 }
const poly a
Definition: syzextra.cc:212
int gf_q1
Definition: gfops.cc:50
int gf_q
Definition: gfops.cc:47
int i
Definition: cfEzgcd.cc:123
const poly b
Definition: syzextra.cc:213
int gf_neg ( int  a)
inline

Definition at line 123 of file gfops.h.

124 {
125  // -z^a=z^a*(-1)=z^a*gf_m1;
126  if ( a == gf_q ) return a;
127  int i = a + gf_m1;
128  if ( i >= gf_q1 )
129  i -= gf_q1;
130  return i;
131 }
const poly a
Definition: syzextra.cc:212
int gf_q1
Definition: gfops.cc:50
int gf_m1
Definition: gfops.cc:51
int gf_q
Definition: gfops.cc:47
int i
Definition: cfEzgcd.cc:123
int gf_one ( )
inline

Definition at line 104 of file gfops.h.

105 {
106  return 0;
107 }
int gf_power ( int  a,
int  n 
)
inline

Definition at line 222 of file gfops.h.

223 {
224  if ( n == 0 )
225  return 0;
226  else if ( n == 1 )
227  return a;
228  else
229  return gf_mul( a, gf_power( a, n-1 ) );
230 }
const poly a
Definition: syzextra.cc:212
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
int gf_mul(int a, int b)
Definition: gfops.h:163
int gf_power(int a, int n)
Definition: gfops.h:222
long gf_power ( long  a,
int  n 
)
inline

Definition at line 232 of file gfops.h.

233 {
234  if ( n == 0 )
235  return 0;
236  else if ( n == 1 )
237  return a;
238  else
239  return gf_mul( a, gf_power( a, n-1 ) );
240 }
const poly a
Definition: syzextra.cc:212
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
int gf_mul(int a, int b)
Definition: gfops.h:163
int gf_power(int a, int n)
Definition: gfops.h:222
void gf_print ( OSTREAM os,
int  a 
)
inline

Definition at line 207 of file gfops.h.

208 {
209  if ( a == gf_q )
210  os << "0";
211  else if ( a == 0 )
212  os << "1";
213  else if ( a == 1 )
214  os << gf_name;
215  else
216  os << gf_name << "^" << a;
217 }
const poly a
Definition: syzextra.cc:212
int gf_q
Definition: gfops.cc:47
char gf_name
Definition: gfops.cc:52
void gf_setcharacteristic ( int  p,
int  n,
char  name 
)

Definition at line 219 of file gfops.cc.

220 {
221  ASSERT( gf_valid_combination( p, n ), "illegal immediate GF(q)" );
222  gf_name = name;
223  gf_get_table( p, n );
224 }
return P p
Definition: myNF.cc:203
static bool gf_valid_combination(int p, int n)
Definition: gfops.cc:196
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
char gf_name
Definition: gfops.cc:52
static void gf_get_table(int p, int n)
Definition: gfops.cc:76
char name(const Variable &v)
Definition: variable.h:95
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int gf_sign ( int  a)
inline

Definition at line 113 of file gfops.h.

114 {
115  if ( gf_iszero( a ) )
116  return 0;
117  else
118  return 1;
119 }
const poly a
Definition: syzextra.cc:212
bool gf_iszero(int a)
Definition: gfops.h:43
int gf_sub ( int  a,
int  b 
)
inline

Definition at line 158 of file gfops.h.

159 {
160  return gf_add( a, gf_neg( b ) );
161 }
const poly a
Definition: syzextra.cc:212
int gf_neg(int a)
Definition: gfops.h:123
int gf_add(int a, int b)
Definition: gfops.h:133
const poly b
Definition: syzextra.cc:213
int gf_zero ( )
inline

Definition at line 99 of file gfops.h.

100 {
101  return gf_q;
102 }
int gf_q
Definition: gfops.cc:47

Variable Documentation

int gf_m1

Definition at line 51 of file gfops.cc.

CanonicalForm gf_mipo
int gf_n

Definition at line 49 of file gfops.cc.

char gf_name

Definition at line 52 of file gfops.cc.

int gf_p

Definition at line 48 of file gfops.cc.

int gf_q

Definition at line 47 of file gfops.cc.

int gf_q1

Definition at line 50 of file gfops.cc.

unsigned short* gf_table

Definition at line 54 of file gfops.cc.