My Project
ffops.h
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  * @file ffops.h
5  *
6  * operations in a finite prime field F_p.
7  * The largest supported p is 536870909, i.e. the largest prime less than 2^29.
8  *
9 **/
10 
11 #ifndef INCL_FFOPS_H
12 #define INCL_FFOPS_H
13 
14 // #include "config.h"
15 
16 #include "cf_globals.h"
17 #ifdef HAVE_NTL
18 #include <NTL/config.h>
19 #endif
20 
21 /* define type of your compilers 64 bit integer type */
22 #ifndef FACTORY_INT64
23 #if SIZEOF_LONG == 8
24 #define FACTORY_INT64 long int
25 #else
26 #define FACTORY_INT64 long long int
27 #endif
28 #endif
29 
34 
35 int ff_newinv ( const int );
36 int ff_biginv ( const int );
37 void ff_setprime ( const int );
38 
39 inline int ff_norm ( const int a )
40 {
41  int n = a % ff_prime;
42 #if defined(NTL_AVOID_BRANCHING)
43  n += (n >> 31) & ff_prime;
44  return n;
45 #else
46  if (n < 0) n += ff_prime;
47  return n;
48 #endif
49 }
50 
51 inline long ff_norm ( const long a )
52 {
53  long n = a % (long)ff_prime;
54 #if defined(NTL_AVOID_BRANCHING)
55  #if SIZEOF_LONG==8
56  n += (n >> 63) & ff_prime;
57  #else
58  n += (n >> 31) & ff_prime;
59  #endif
60  return n;
61 #else
62  if (n < 0) n += (long)ff_prime;
63  return n;
64 #endif
65 }
66 
67 inline int ff_symmetric( const int a )
68 {
70  return ( a > ff_halfprime ) ? a - ff_prime : a;
71  else
72  return a;
73 }
74 
75 inline long ff_symmetric( const long a )
76 {
78  return ( a > ff_halfprime ) ? a - ff_prime : a;
79  else
80  return a;
81 }
82 
83 #if SIZEOF_LONG==4
84 inline int ff_bignorm ( const FACTORY_INT64 a )
85 {
86  int n = (int)(a % (FACTORY_INT64)ff_prime);
87 #if defined(NTL_AVOID_BRANCHING)
88  n += (n >> 31) & ff_prime;
89  return n;
90 #else
91  if (n < 0) n += ff_prime;
92  return n;
93 #endif
94 }
95 #endif
96 
97 inline int ff_add ( const int a, const int b )
98 {
99  //return ff_norm( a + b );
100 #if defined(NTL_AVOID_BRANCHING)
101  int r=( a + b );
102  r -= ff_prime;
103  r += (r >> 31) & ff_prime;
104  return r;
105 #else
106  int r=( a + b );
107  if (r >= ff_prime) r -= ff_prime;
108  return r;
109 #endif
110 }
111 
112 inline int ff_sub ( const int a, const int b )
113 {
114  //return ff_norm( a - b );
115 #if defined(NTL_AVOID_BRANCHING)
116  int r=( a - b );
117  r += (r >> 31) & ff_prime;
118  return r;
119 #else
120  int r=( a - b );
121  if (r < 0) r += ff_prime;
122  return r;
123 #endif
124 }
125 
126 inline int ff_neg ( const int a )
127 {
128  //return ff_norm( -a );
129 // EXPERIMENT
130 #if defined(NTL_AVOID_BRANCHING)
131  int r= -a;
132  r += (r >> 31) & ff_prime;
133  return r;
134 #else
135  return ( a == 0 ? 0 : ff_prime-a );
136 #endif
137 }
138 
139 inline int ff_mul ( const int a, const int b )
140 {
141 #if SIZEOF_LONG==4
142  if ( ff_big )
143  return ff_bignorm( (FACTORY_INT64)a * (FACTORY_INT64)b );
144  else
145 #endif /* else: FACTORY_INT64 is long, i.e. ff_bignorm is the same as ff_norm(long) */
146  return ff_norm ( (long)a * (long)b );
147 }
148 
149 inline int ff_inv ( const int a )
150 {
151  if ( ff_big )
152  return ff_biginv( a );
153  else {
154  int b;
155  if ( (b = (int)(ff_invtab[a])) )
156  return b;
157  else
158  return ff_newinv( a );
159  }
160 
161 }
162 
163 inline int ff_div ( const int a, const int b )
164 {
165  return ff_mul( a, ff_inv( b ) );
166 }
167 
168 #endif /* ! INCL_FFOPS_H */
CanonicalForm b
Definition: cfModGcd.cc:4103
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: cf_defs.h:33
INST_VAR CFSwitches cf_glob_switches
Definition: cf_switches.cc:54
bool isOn(int s) const
check if 's' is on
Definition: cf_switches.h:55
#define FACTORY_INT64
Definition: ffops.h:24
int ff_norm(const int a)
Definition: ffops.h:39
int ff_symmetric(const int a)
Definition: ffops.h:67
EXTERN_VAR int ff_prime
Definition: ffops.h:30
EXTERN_VAR int ff_halfprime
Definition: ffops.h:31
void ff_setprime(const int)
Definition: ffops.cc:19
int ff_inv(const int a)
Definition: ffops.h:149
EXTERN_VAR bool ff_big
Definition: ffops.h:33
int ff_biginv(const int)
Definition: ffops.cc:72
EXTERN_VAR short * ff_invtab
Definition: ffops.h:32
int ff_add(const int a, const int b)
Definition: ffops.h:97
int ff_div(const int a, const int b)
Definition: ffops.h:163
int ff_mul(const int a, const int b)
Definition: ffops.h:139
int ff_newinv(const int)
Definition: ffops.cc:30
int ff_neg(const int a)
Definition: ffops.h:126
int ff_sub(const int a, const int b)
Definition: ffops.h:112
#define EXTERN_VAR
Definition: globaldefs.h:6