My Project
Loading...
Searching...
No Matches
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)
 
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_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
VAR char gf_name
Definition: gfops.cc:52
static void gf_get_table(int p, int n)
Definition: gfops.cc:76
int name
New type name for int.
Definition: templateForC.h:21

◆ 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.