My Project  debian-1:4.1.1-p2+ds-4build4
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 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

◆ FACTORY_INT64

#define FACTORY_INT64   long int

Definition at line 24 of file ffops.h.

Function Documentation

◆ ff_add()

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

Definition at line 107 of file ffops.h.

108 {
109  //return ff_norm( a + b );
110 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
111  int r=( a + b );
112  r -= ff_prime;
113  r += (r >> 31) & ff_prime;
114  return r;
115 #else
116  int r=( a + b );
117  if (r >= ff_prime) r -= ff_prime;
118  return r;
119 #endif
120 }
CanonicalForm b
Definition: cfModGcd.cc:4044
int ff_prime
Definition: ffops.cc:14

◆ ff_biginv()

int ff_biginv ( const int  a)

Definition at line 71 of file ffops.cc.

72 {
73  if (a < 2)
74  return a;
75  int p, q, r1, r2, y1, y2;
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 }
int p
Definition: cfModGcd.cc:4019
int ff_prime
Definition: ffops.cc:14

◆ ff_bignorm()

int ff_bignorm ( const FACTORY_INT64  a)
inline

Definition at line 95 of file ffops.h.

96 {
97  int n = (int)(a % (FACTORY_INT64)ff_prime);
98 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
99  n += (n >> 31) & ff_prime;
100  return n;
101 #else
102  if (n < 0) n += ff_prime;
103  return n;
104 #endif
105 }
#define FACTORY_INT64
Definition: ffops.h:24

◆ ff_div()

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

Definition at line 171 of file ffops.h.

172 {
173  return ff_mul( a, ff_inv( b ) );
174 }
int ff_inv(const int a)
Definition: ffops.h:157
int ff_mul(const int a, const int b)
Definition: ffops.h:149

◆ ff_inv()

int ff_inv ( const int  a)
inline

Definition at line 157 of file ffops.h.

158 {
159  if ( ff_big )
160  return ff_biginv( a );
161  else {
162  register int b;
163  if ( (b = (int)(ff_invtab[a])) )
164  return b;
165  else
166  return ff_newinv( a );
167  }
168 
169 }
short * ff_invtab
Definition: ffops.cc:17
int ff_biginv(const int)
Definition: ffops.cc:71
bool ff_big
Definition: ffops.cc:16
int ff_newinv(const int)
Definition: ffops.cc:29

◆ ff_longnorm()

int ff_longnorm ( const long  a)
inline

Definition at line 83 of file ffops.h.

84 {
85  int n = (int)(a % (long)ff_prime);
86 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
87  n += (n >> 31) & ff_prime;
88  return n;
89 #else
90  if (n < 0) n += ff_prime;
91  return n;
92 #endif
93 }

◆ ff_mul()

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

Definition at line 149 of file ffops.h.

150 {
151  if ( ff_big )
152  return ff_bignorm( (FACTORY_INT64)a * (FACTORY_INT64)b );
153  else
154  return ff_longnorm ( (long)a * (long)b );
155 }
int ff_bignorm(const FACTORY_INT64 a)
Definition: ffops.h:95
int ff_longnorm(const long a)
Definition: ffops.h:83

◆ ff_neg()

int ff_neg ( const int  a)
inline

Definition at line 136 of file ffops.h.

137 {
138  //return ff_norm( -a );
139 // EXPERIMENT
140 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
141  int r= -a;
142  r += (r >> 31) & ff_prime;
143  return r;
144 #else
145  return ( a == 0 ? 0 : ff_prime-a );
146 #endif
147 }

◆ ff_newinv()

int ff_newinv ( const int  a)

Definition at line 29 of file ffops.cc.

30 {
31  if (a < 2)
32  return (ff_invtab[a] = a);
33  int p, q, r1, r2, y1, y2;
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 }
short * ff_invtab
Definition: ffops.cc:17

◆ ff_norm() [1/2]

int ff_norm ( const int  a)
inline

Definition at line 39 of file ffops.h.

40 {
41  int n = a % ff_prime;
42 #if defined(i386) || defined(__x86_64__) || 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 }

◆ ff_norm() [2/2]

long ff_norm ( const long  a)
inline

Definition at line 51 of file ffops.h.

52 {
53  long n = a % ff_prime;
54 #if defined(i386) || defined(__x86_64__) || 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 += ff_prime;
63  return n;
64 #endif
65 }

◆ ff_setprime()

void ff_setprime ( const int  p)

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 }
int ff_halfprime
Definition: ffops.cc:15
bool ff_big
Definition: ffops.cc:16

◆ ff_sub()

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

Definition at line 122 of file ffops.h.

123 {
124  //return ff_norm( a - b );
125 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
126  int r=( a - b );
127  r += (r >> 31) & ff_prime;
128  return r;
129 #else
130  int r=( a - b );
131  if (r < 0) r += ff_prime;
132  return r;
133 #endif
134 }

◆ ff_symmetric() [1/2]

int ff_symmetric ( const int  a)
inline

Definition at line 67 of file ffops.h.

68 {
70  return ( a > ff_halfprime ) ? a - ff_prime : a;
71  else
72  return a;
73 }
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: cf_defs.h:30
CFSwitches cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.cc:41
bool isOn(int s) const
check if 's' is on
Definition: cf_switches.h:55
int ff_halfprime
Definition: ffops.cc:15

◆ ff_symmetric() [2/2]

long ff_symmetric ( const long  a)
inline

Definition at line 75 of file ffops.h.

76 {
78  return ( a > ff_halfprime ) ? a - ff_prime : a;
79  else
80  return a;
81 }

Variable Documentation

◆ ff_big

bool ff_big
extern

Definition at line 16 of file ffops.cc.

◆ ff_halfprime

int ff_halfprime
extern

Definition at line 15 of file ffops.cc.

◆ ff_invtab

short* ff_invtab
extern

Definition at line 17 of file ffops.cc.

◆ ff_prime

int ff_prime
extern

Definition at line 14 of file ffops.cc.