My Project
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

EXTERN_VAR int gf_q
 
EXTERN_VAR int gf_p
 
EXTERN_VAR int gf_n
 
EXTERN_VAR int gf_q1
 
EXTERN_VAR int gf_m1
 
EXTERN_VAR char gf_name
 
EXTERN_VAR unsigned short * gf_table
 
EXTERN_INST_VAR 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

◆ OSTREAM

#define OSTREAM   std::ostream

Definition at line 19 of file gfops.h.

Function Documentation

◆ gf_add()

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 }
CanonicalForm b
Definition: cfModGcd.cc:4103
EXTERN_VAR int gf_q
Definition: gfops.h:31
EXTERN_VAR unsigned short * gf_table
Definition: gfops.h:38
EXTERN_VAR int gf_q1
Definition: gfops.h:34

◆ gf_div()

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 }
#define ASSERT(expression, message)
Definition: cf_assert.h:99
const CanonicalForm int s
Definition: facAbsFact.cc:51

◆ gf_gf2ff() [1/2]

int gf_gf2ff ( int  a)

Definition at line 231 of file gfops.cc.

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

◆ gf_gf2ff() [2/2]

long gf_gf2ff ( long  a)

Definition at line 209 of file gfops.cc.

210 {
211  if ( gf_iszero( a ) )
212  return 0;
213  else
214  {
215  // starting from z^0=1, step through the table
216  // counting the steps until we hit z^a or z^0
217  // again. since we are working in char(p), the
218  // latter is guaranteed to be fulfilled.
219  long i = 0, ff = 1;
220  do
221  {
222  if ( i == a )
223  return ff;
224  ff++;
225  i = gf_table[i];
226  } while ( i != 0 );
227  return -1;
228  }
229 }

◆ gf_int2gf() [1/2]

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 }
EXTERN_VAR int gf_p
Definition: gfops.h:32

◆ gf_int2gf() [2/2]

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 }

◆ gf_inv()

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 }

◆ gf_isff() [1/2]

bool gf_isff ( int  a)

Definition at line 264 of file gfops.cc.

265 {
266  if ( gf_iszero( a ) )
267  return true;
268  else
269  {
270  // z^a in GF(p) iff (z^a)^p-1=1
271  return gf_isone( gf_power( a, gf_p - 1 ) );
272  }
273 }
VAR int gf_p
Definition: gfops.cc:48
bool gf_isone(int a)
Definition: gfops.h:53
int gf_power(int a, int n)
Definition: gfops.h:222

◆ gf_isff() [2/2]

bool gf_isff ( long  a)

Definition at line 253 of file gfops.cc.

254 {
255  if ( gf_iszero( a ) )
256  return true;
257  else
258  {
259  // z^a in GF(p) iff (z^a)^p-1=1
260  return gf_isone( gf_power( a, gf_p - 1 ) );
261  }
262 }

◆ gf_isone() [1/2]

bool gf_isone ( int  a)
inline

Definition at line 53 of file gfops.h.

54 {
55  return 0 == a;
56 }

◆ gf_isone() [2/2]

bool gf_isone ( long  a)
inline

Definition at line 58 of file gfops.h.

59 {
60  return 0 == a;
61 }

◆ gf_iszero() [1/2]

bool gf_iszero ( int  a)
inline

Definition at line 43 of file gfops.h.

44 {
45  return gf_q == a;
46 }

◆ gf_iszero() [2/2]

bool gf_iszero ( long  a)
inline

Definition at line 48 of file gfops.h.

49 {
50  return gf_q == a;
51 }

◆ gf_mul() [1/2]

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 }

◆ gf_mul() [2/2]

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 }

◆ gf_neg()

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 }
EXTERN_VAR int gf_m1
Definition: gfops.h:35

◆ gf_one()

int gf_one ( )
inline

Definition at line 104 of file gfops.h.

105 {
106  return 0;
107 }

◆ gf_power() [1/2]

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 }
int gf_mul(int a, int b)
Definition: gfops.h:163

◆ gf_power() [2/2]

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 }

◆ gf_print()

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 }
EXTERN_VAR char gf_name
Definition: gfops.h:36

◆ gf_setcharacteristic()

void gf_setcharacteristic ( int  p,
int  n,
char  name 
)

Definition at line 202 of file gfops.cc.

203 {
204  ASSERT( gf_valid_combination( p, n ), "illegal immediate GF(q)" );
205  gf_name = name;
206  gf_get_table( p, n );
207 }
int p
Definition: cfModGcd.cc:4078
char name(const Variable &v)
Definition: factory.h:189
VAR char gf_name
Definition: gfops.cc:52
static void gf_get_table(int p, int n)
Definition: gfops.cc:76

◆ gf_sign()

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 }

◆ gf_sub()

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 }
int gf_neg(int a)
Definition: gfops.h:123
int gf_add(int a, int b)
Definition: gfops.h:133

◆ gf_zero()

int gf_zero ( )
inline

Definition at line 99 of file gfops.h.

100 {
101  return gf_q;
102 }

Variable Documentation

◆ gf_m1

EXTERN_VAR int gf_m1

Definition at line 35 of file gfops.h.

◆ gf_mipo

Definition at line 40 of file gfops.h.

◆ gf_n

EXTERN_VAR int gf_n

Definition at line 33 of file gfops.h.

◆ gf_name

EXTERN_VAR char gf_name

Definition at line 36 of file gfops.h.

◆ gf_p

EXTERN_VAR int gf_p

Definition at line 32 of file gfops.h.

◆ gf_q

EXTERN_VAR int gf_q

Definition at line 31 of file gfops.h.

◆ gf_q1

EXTERN_VAR int gf_q1

Definition at line 34 of file gfops.h.

◆ gf_table

EXTERN_VAR unsigned short* gf_table

Definition at line 38 of file gfops.h.