Loading...
Searching...
No Matches
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.

{
// z^a+z^b=z^b*(z^(a-b)+1), if a>=b;
// =z^a*(z^(b-a)+1), if a<b;
if ( a == gf_q ) return b;
if ( b == gf_q ) return a;
int zb, zab, r;
if ( a >= b ) {
zb = b;
zab = a - b;
}
else {
zb = a;
zab = b - a;
}
if ( gf_table[zab] == gf_q )
r = gf_q; /*if z^(a-b)+1 =0*/
else {
r= zb + gf_table[zab];
if ( r >= gf_q1 )
r -= gf_q1;
}
return r;
}
b
CanonicalForm b
Definition cfModGcd.cc:4111
gf_q
VAR int gf_q
Definition gfops.cc:47
gf_table
VAR unsigned short * gf_table
Definition gfops.cc:54
gf_q1
VAR int gf_q1
Definition gfops.cc:50

## gf_div()

int gf_div | ( | int | a,
|  | int | b )

inline

Definition at line 185 of file gfops.h.

{
ASSERT( b != gf_q, "divide by zero" );
if ( a == gf_q )
return gf_q;
else {
int s = a - b;
if (s < 0)
s += gf_q1;
return s;
}
}
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
s
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.

{
if ( gf_iszero( a ) )
return 0;
else
{
// starting from z^0=1, step through the table
// counting the steps until we hit z^a or z^0
// again. since we are working in char(p), the
// latter is guaranteed to be fulfilled.
int i = 0, ff = 1;
do
{
if ( i == a )
return ff;
ff++;
i = gf_table[i];
} while ( i != 0 );
return -1;
}
}
i
int i
Definition cfEzgcd.cc:132
gf_iszero
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.

{
if ( gf_iszero( a ) )
return 0;
else
{
// starting from z^0=1, step through the table
// counting the steps until we hit z^a or z^0
// again. since we are working in char(p), the
// latter is guaranteed to be fulfilled.
long i = 0, ff = 1;
do
{
if ( i == a )
return ff;
ff++;
i = gf_table[i];
} while ( i != 0 );
return -1;
}
}

## gf_int2gf() [1/2]

int gf_int2gf | ( | int | i | ) |

inline

Definition at line 65 of file gfops.h.

{
while ( i < 0 )
i += gf_p;
while ( i >= gf_p )
i -= gf_p;
if ( i == 0 )
return gf_q;
int c = 0;
while ( i > 1 ) {
c = gf_table[c];
i--;
}
return c;
}
gf_p
VAR int gf_p
Definition gfops.cc:48

## gf_int2gf() [2/2]

long gf_int2gf | ( | long | i | ) |

inline

Definition at line 81 of file gfops.h.

{
while ( i < 0 )
i += gf_p;
while ( i >= gf_p )
i -= gf_p;
if ( i == 0 )
return gf_q;
long c = 0;
while ( i > 1 ) {
c = gf_table[c];
i--;
}
return c;
}

## gf_inv()

int gf_inv | ( | int | a | ) |

inline

Definition at line 198 of file gfops.h.

{
ASSERT( a != gf_q, "divide by zero" );
return gf_q1 - a;
}

## gf_isff() [1/2]

bool gf_isff | ( | int | a | ) |

Definition at line 264 of file gfops.cc.

{
if ( gf_iszero( a ) )
return true;
else
{
// z^a in GF(p) iff (z^a)^p-1=1
return gf_isone( gf_power( a, gf_p - 1 ) );
}
}
gf_isone
bool gf_isone(int a)
Definition gfops.h:53
gf_power
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.

{
if ( gf_iszero( a ) )
return true;
else
{
// z^a in GF(p) iff (z^a)^p-1=1
return gf_isone( gf_power( a, gf_p - 1 ) );
}
}

## gf_isone() [1/2]

bool gf_isone | ( | int | a | ) |

inline

Definition at line 53 of file gfops.h.

{
return 0 == a;
}

## gf_isone() [2/2]

bool gf_isone | ( | long | a | ) |

inline

Definition at line 58 of file gfops.h.

{
return 0 == a;
}

## gf_iszero() [1/2]

bool gf_iszero | ( | int | a | ) |

inline

Definition at line 43 of file gfops.h.

{
return gf_q == a;
}

## gf_iszero() [2/2]

bool gf_iszero | ( | long | a | ) |

inline

Definition at line 48 of file gfops.h.

{
return gf_q == a;
}

## gf_mul() [1/2]

int gf_mul | ( | int | a,
|  | int | b )

inline

Definition at line 163 of file gfops.h.

{
if ( a == gf_q || b == gf_q )
return gf_q;
else {
int i = a + b;
if ( i >= gf_q1 ) i -= gf_q1;
return i;
}
}

## gf_mul() [2/2]

long gf_mul | ( | long | a,
|  | int | b )

inline

Definition at line 174 of file gfops.h.

{
if ( a == gf_q || b == gf_q )
return gf_q;
else {
long i = a + b;
if ( i >= gf_q1 ) i -= gf_q1;
return i;
}
}

## gf_neg()

int gf_neg | ( | int | a | ) |

inline

Definition at line 123 of file gfops.h.

{
// -z^a=z^a*(-1)=z^a*gf_m1;
if ( a == gf_q ) return a;
int i = a + gf_m1;
if ( i >= gf_q1 )
i -= gf_q1;
return i;
}
gf_m1
VAR int gf_m1
Definition gfops.cc:51

## gf_one()

int gf_one | ( |  | ) |

inline

Definition at line 104 of file gfops.h.

{
return 0;
}

## gf_power() [1/2]

int gf_power | ( | int | a,
|  | int | n )

inline

Definition at line 222 of file gfops.h.

{
if ( n == 0 )
return 0;
else if ( n == 1 )
return a;
else
return gf_mul( a, gf_power( a, n-1 ) );
}
gf_mul
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.

{
if ( n == 0 )
return 0;
else if ( n == 1 )
return a;
else
return gf_mul( a, gf_power( a, n-1 ) );
}

## gf_print()

void gf_print | ( | OSTREAM & | os,
|  | int | a )

inline

Definition at line 207 of file gfops.h.

{
if ( a == gf_q )
os << "0";
else if ( a == 0 )
os << "1";
else if ( a == 1 )
os << gf_name;
else
os << gf_name << "^" << a;
}
gf_name
VAR char gf_name
Definition gfops.cc:52

## gf_setcharacteristic()

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

Definition at line 202 of file gfops.cc.

{
ASSERT( gf_valid_combination( p, n ), "illegal immediate GF(q)" );
gf_name = name;
gf_get_table( p, n );
}
p
int p
Definition cfModGcd.cc:4086
name
char name(const Variable &v)
Definition factory.h:189
gf_get_table
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.

{
if ( gf_iszero( a ) )
return 0;
else
return 1;
}

## gf_sub()

int gf_sub | ( | int | a,
|  | int | b )

inline

Definition at line 158 of file gfops.h.

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

{
return gf_q;
}

## Variable Documentation

## gf_m1

EXTERN_VAR int gf_m1

Definition at line 35 of file gfops.h.

## gf_mipo

EXTERN_INST_VAR CanonicalForm 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.