Macros | Functions | Variables
ffops.h File Reference

operations in a finite prime field F_p. More...

#include "cf_globals.h"
#include <NTL/config.h>

Go to the source code of this file.

Macros

#define FACTORY_INT64   long long int
 

Functions

int ff_newinv (const int)
 
int ff_biginv (const int)
 
void ff_setprime (const int)
 
int ff_norm (const int a)
 
long ff_norm (const long a)
 
int ff_symmetric (const int a)
 
long ff_symmetric (const long a)
 
int ff_longnorm (const long a)
 
int ff_bignorm (const FACTORY_INT64 a)
 
int ff_add (const int a, const int b)
 
int ff_sub (const int a, const int b)
 
int ff_neg (const int a)
 
int ff_mul (const int a, const int b)
 
int ff_inv (const int a)
 
int ff_div (const int a, const int b)
 

Variables

int ff_prime
 
int ff_halfprime
 
short * ff_invtab
 
bool ff_big
 

Detailed Description

operations in a finite prime field F_p.

The largest supported p is 536870909, i.e. the largest prime less than 2^29.

Definition in file ffops.h.

Macro Definition Documentation

#define FACTORY_INT64   long long int

Definition at line 23 of file ffops.h.

Function Documentation

int ff_add ( const int  a,
const int  b 
)
inline

Definition at line 99 of file ffops.h.

100 {
101  //return ff_norm( a + b );
102 #if defined(i386) || defined(NTL_AVOID_BRANCHING)
103  int r=( a + b );
104  r -= ff_prime;
105  r += (r >> 31) & ff_prime;
106  return r;
107 #else
108  int r=( a + b );
109  if (r >= ff_prime) r -= ff_prime;
110  return r;
111 #endif
112 }
const poly a
Definition: syzextra.cc:212
int ff_prime
Definition: ffops.cc:14
const ring r
Definition: syzextra.cc:208
const poly b
Definition: syzextra.cc:213
int ff_biginv ( const int  )

Definition at line 71 of file ffops.cc.

72 {
73  int p, q, r1, r2, y1, y2;
74  if (a < 2)
75  return a;
76  r1 = p = ff_prime;
77  q = r1 / a;
78  y1 = -q;
79  r1 -= a * q;
80  if (r1 == 1)
81  return p + y1;
82  r2 = a;
83  y2 = 1;
84  for (;;)
85  {
86  q = r2 / r1;
87  y2 -= y1 * q;
88  r2 -= r1 * q;
89  if (r2 == 1)
90  {
91  if (y2 > 0)
92  return y2;
93  else
94  return p + y2;
95  }
96  q = r1 / r2;
97  y1 -= y2 * q;
98  r1 -= r2 * q;
99  if (r1 == 1)
100  {
101  if (y1 > 0)
102  return y1;
103  else
104  return p + y1;
105  }
106  }
107 }
const poly a
Definition: syzextra.cc:212
return P p
Definition: myNF.cc:203
int ff_prime
Definition: ffops.cc:14
int ff_bignorm ( const FACTORY_INT64  a)
inline

Definition at line 87 of file ffops.h.

88 {
89  int n = (int)(a % (FACTORY_INT64)ff_prime);
90 #if defined(i386) || defined(NTL_AVOID_BRANCHING)
91  n += (n >> 31) & ff_prime;
92  return n;
93 #else
94  if (n < 0) n += ff_prime;
95  return n;
96 #endif
97 }
const poly a
Definition: syzextra.cc:212
int ff_prime
Definition: ffops.cc:14
#define FACTORY_INT64
Definition: ffops.h:23
int ff_div ( const int  a,
const int  b 
)
inline

Definition at line 163 of file ffops.h.

164 {
165  return ff_mul( a, ff_inv( b ) );
166 }
const poly a
Definition: syzextra.cc:212
int ff_mul(const int a, const int b)
Definition: ffops.h:141
int ff_inv(const int a)
Definition: ffops.h:149
const poly b
Definition: syzextra.cc:213
int ff_inv ( const int  a)
inline

Definition at line 149 of file ffops.h.

150 {
151  if ( ff_big )
152  return ff_biginv( a );
153  else {
154  register int b;
155  if ( (b = (int)(ff_invtab[a])) )
156  return b;
157  else
158  return ff_newinv( a );
159  }
160 
161 }
const poly a
Definition: syzextra.cc:212
short * ff_invtab
Definition: ffops.cc:17
int ff_newinv(const int)
Definition: ffops.cc:29
bool ff_big
Definition: ffops.cc:16
int ff_biginv(const int)
Definition: ffops.cc:71
const poly b
Definition: syzextra.cc:213
int ff_longnorm ( const long  a)
inline

Definition at line 75 of file ffops.h.

76 {
77  int n = (int)(a % (long)ff_prime);
78 #if defined(i386) || defined(NTL_AVOID_BRANCHING)
79  n += (n >> 31) & ff_prime;
80  return n;
81 #else
82  if (n < 0) n += ff_prime;
83  return n;
84 #endif
85 }
const poly a
Definition: syzextra.cc:212
int ff_prime
Definition: ffops.cc:14
int ff_mul ( const int  a,
const int  b 
)
inline

Definition at line 141 of file ffops.h.

142 {
143  if ( ff_big )
144  return ff_bignorm( (FACTORY_INT64)a * (FACTORY_INT64)b );
145  else
146  return ff_longnorm ( (long)a * (long)b );
147 }
const poly a
Definition: syzextra.cc:212
int ff_bignorm(const FACTORY_INT64 a)
Definition: ffops.h:87
bool ff_big
Definition: ffops.cc:16
int ff_longnorm(const long a)
Definition: ffops.h:75
const poly b
Definition: syzextra.cc:213
#define FACTORY_INT64
Definition: ffops.h:23
int ff_neg ( const int  a)
inline

Definition at line 128 of file ffops.h.

129 {
130  //return ff_norm( -a );
131 // EXPERIMENT
132 #if defined(i386) || defined(NTL_AVOID_BRANCHING)
133  int r= -a;
134  r += (r >> 31) & ff_prime;
135  return r;
136 #else
137  return ( a == 0 ? 0 : ff_prime-a );
138 #endif
139 }
const poly a
Definition: syzextra.cc:212
int ff_prime
Definition: ffops.cc:14
const ring r
Definition: syzextra.cc:208
int ff_newinv ( const int  )

Definition at line 29 of file ffops.cc.

30 {
31  int p, q, r1, r2, y1, y2;
32  if (a < 2)
33  return (ff_invtab[a] = a);
34  r1 = p = ff_prime;
35  q = r1 / a;
36  y1 = -q;
37  r1 -= a * q;
38  if (r1 == 1)
39  {
40  y1 += p;
41  ff_invtab[y1] = a;
42  return (ff_invtab[a] = y1);
43  }
44  r2 = a;
45  y2 = 1;
46  for (;;)
47  {
48  q = r2 / r1;
49  y2 -= y1 * q;
50  r2 -= r1 * q;
51  if (r2 == 1)
52  {
53  if (y2 < 0)
54  y2 += p;
55  ff_invtab[y2] = a;
56  return (ff_invtab[a] = y2);
57  }
58  q = r1 / r2;
59  y1 -= y2 * q;
60  r1 -= r2 * q;
61  if (r1 == 1)
62  {
63  if (y1 < 0)
64  y1 += p;
65  ff_invtab[y1] = a;
66  return (ff_invtab[a] = y1);
67  }
68  }
69 }
const poly a
Definition: syzextra.cc:212
return P p
Definition: myNF.cc:203
short * ff_invtab
Definition: ffops.cc:17
int ff_prime
Definition: ffops.cc:14
int ff_norm ( const int  a)
inline

Definition at line 35 of file ffops.h.

36 {
37  int n = a % ff_prime;
38 #if defined(i386) || defined(NTL_AVOID_BRANCHING)
39  n += (n >> 31) & ff_prime;
40  return n;
41 #else
42  if (n < 0) n += ff_prime;
43  return n;
44 #endif
45 }
const poly a
Definition: syzextra.cc:212
int ff_prime
Definition: ffops.cc:14
long ff_norm ( const long  a)
inline

Definition at line 47 of file ffops.h.

48 {
49  long n = a % ff_prime;
50 #if defined(i386) || defined(NTL_AVOID_BRANCHING)
51  n += (n >> 31) & ff_prime;
52  return n;
53 #else
54  if (n < 0) n += ff_prime;
55  return n;
56 #endif
57 }
const poly a
Definition: syzextra.cc:212
int ff_prime
Definition: ffops.cc:14
void ff_setprime ( const int  )

Definition at line 19 of file ffops.cc.

20 {
21  if ( p != ff_prime ) {
22  ff_prime = p;
23  ff_halfprime = ff_prime / 2;
24  if ( ! ff_big )
25  memset( ff_invtab, 0, ff_prime*sizeof(short) );
26  }
27 }
return P p
Definition: myNF.cc:203
short * ff_invtab
Definition: ffops.cc:17
bool ff_big
Definition: ffops.cc:16
int ff_halfprime
Definition: ffops.cc:15
int ff_prime
Definition: ffops.cc:14
int ff_sub ( const int  a,
const int  b 
)
inline

Definition at line 114 of file ffops.h.

115 {
116  //return ff_norm( a - b );
117 #if defined(i386) || defined(NTL_AVOID_BRANCHING)
118  int r=( a - b );
119  r += (r >> 31) & ff_prime;
120  return r;
121 #else
122  int r=( a - b );
123  if (r < 0) r += ff_prime;
124  return r;
125 #endif
126 }
const poly a
Definition: syzextra.cc:212
int ff_prime
Definition: ffops.cc:14
const ring r
Definition: syzextra.cc:208
const poly b
Definition: syzextra.cc:213
int ff_symmetric ( const int  a)
inline

Definition at line 59 of file ffops.h.

60 {
61  if ( cf_glob_switches.isOn( SW_SYMMETRIC_FF ) )
62  return ( a > ff_halfprime ) ? a - ff_prime : a;
63  else
64  return a;
65 }
const poly a
Definition: syzextra.cc:212
int ff_halfprime
Definition: ffops.cc:15
int ff_prime
Definition: ffops.cc:14
#define cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.h:75
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: cf_defs.h:30
long ff_symmetric ( const long  a)
inline

Definition at line 67 of file ffops.h.

68 {
69  if ( cf_glob_switches.isOn( SW_SYMMETRIC_FF ) )
70  return ( a > ff_halfprime ) ? a - ff_prime : a;
71  else
72  return a;
73 }
const poly a
Definition: syzextra.cc:212
int ff_halfprime
Definition: ffops.cc:15
int ff_prime
Definition: ffops.cc:14
#define cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.h:75
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: cf_defs.h:30

Variable Documentation

bool ff_big

Definition at line 16 of file ffops.cc.

int ff_halfprime

Definition at line 15 of file ffops.cc.

short* ff_invtab

Definition at line 17 of file ffops.cc.

int ff_prime

Definition at line 14 of file ffops.cc.