My Project
Loading...
Searching...
No Matches
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
35int ff_newinv ( const int );
36int ff_biginv ( const int );
37void ff_setprime ( const int );
38
39inline 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
51inline 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
67inline int ff_symmetric( const int a )
68{
70 return ( a > ff_halfprime ) ? a - ff_prime : a;
71 else
72 return a;
73}
74
75inline 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
84inline 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
97inline 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
112inline 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
126inline 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
139inline 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
149inline 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
163inline 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