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 #define FACTORY_INT64 long long int
24 #endif
25 
26 extern int ff_prime;
27 extern int ff_halfprime;
28 extern short * ff_invtab;
29 extern bool ff_big;
30 
31 int ff_newinv ( const int );
32 int ff_biginv ( const int );
33 void ff_setprime ( const int );
34 
35 inline int ff_norm ( const int a )
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 }
46 
47 inline long ff_norm ( const long a )
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 }
58 
59 inline int ff_symmetric( const int a )
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 }
66 
67 inline long ff_symmetric( const long a )
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 }
74 
75 inline int ff_longnorm ( const long a )
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 }
86 
87 inline int ff_bignorm ( const FACTORY_INT64 a )
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 }
98 
99 inline int ff_add ( const int a, const int b )
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 }
113 
114 inline int ff_sub ( const int a, const int b )
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 }
127 
128 inline int ff_neg ( const int a )
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 }
140 
141 inline int ff_mul ( const int a, const int b )
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 }
148 
149 inline int ff_inv ( const int a )
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 }
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 */
const poly a
Definition: syzextra.cc:212
int ff_halfprime
Definition: ffops.cc:15
short * ff_invtab
Definition: ffops.cc:17
int ff_newinv(const int)
Definition: ffops.cc:29
void ff_setprime(const int)
Definition: ffops.cc:19
int ff_mul(const int a, const int b)
Definition: ffops.h:141
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
int ff_bignorm(const FACTORY_INT64 a)
Definition: ffops.h:87
bool ff_big
Definition: ffops.cc:16
int ff_prime
Definition: ffops.cc:14
int ff_norm(const int a)
Definition: ffops.h:35
int ff_biginv(const int)
Definition: ffops.cc:71
int ff_div(const int a, const int b)
Definition: ffops.h:163
const ring r
Definition: syzextra.cc:208
int ff_sub(const int a, const int b)
Definition: ffops.h:114
int ff_neg(const int a)
Definition: ffops.h:128
int ff_add(const int a, const int b)
Definition: ffops.h:99
#define cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.h:75
int ff_inv(const int a)
Definition: ffops.h:149
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: cf_defs.h:30
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_symmetric(const int a)
Definition: ffops.h:59