My Project  debian-1:4.1.2-p1+ds-2
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_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

EXTERN_VAR int ff_prime
 
EXTERN_VAR int ff_halfprime
 
EXTERN_VAR short * ff_invtab
 
EXTERN_VAR 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 97 of file ffops.h.

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 }
CanonicalForm b
Definition: cfModGcd.cc:4044
EXTERN_VAR int ff_prime
Definition: ffops.h:30

◆ ff_biginv()

int ff_biginv ( const int  a)

Definition at line 72 of file ffops.cc.

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

◆ ff_div()

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 }
int ff_inv(const int a)
Definition: ffops.h:149
int ff_mul(const int a, const int b)
Definition: ffops.h:139

◆ ff_inv()

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 }
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_newinv(const int)
Definition: ffops.cc:30

◆ ff_mul()

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

Definition at line 139 of file ffops.h.

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 }
#define FACTORY_INT64
Definition: ffops.h:24
int ff_norm(const int a)
Definition: ffops.h:39

◆ ff_neg()

int ff_neg ( const int  a)
inline

Definition at line 126 of file ffops.h.

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 }

◆ ff_newinv()

int ff_newinv ( const int  a)

Definition at line 30 of file ffops.cc.

31 {
32  if (a < 2)
33  return (ff_invtab[a] = a);
34  int p, q, r1, r2, y1, y2;
35  r1 = p = ff_prime;
36  q = r1 / a;
37  y1 = -q;
38  r1 -= a * q;
39  if (r1 == 1)
40  {
41  y1 += p;
42  ff_invtab[y1] = a;
43  return (ff_invtab[a] = y1);
44  }
45  r2 = a;
46  y2 = 1;
47  for (;;)
48  {
49  q = r2 / r1;
50  y2 -= y1 * q;
51  r2 -= r1 * q;
52  if (r2 == 1)
53  {
54  if (y2 < 0)
55  y2 += p;
56  ff_invtab[y2] = a;
57  return (ff_invtab[a] = y2);
58  }
59  q = r1 / r2;
60  y1 -= y2 * q;
61  r1 -= r2 * q;
62  if (r1 == 1)
63  {
64  if (y1 < 0)
65  y1 += p;
66  ff_invtab[y1] = a;
67  return (ff_invtab[a] = y1);
68  }
69  }
70 }
VAR 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(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 % (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 }

◆ ff_setprime()

void ff_setprime ( const int  p)

Definition at line 19 of file ffops.cc.

20 {
21  if ( p != ff_prime )
22  {
23  ff_prime = p;
24  ff_halfprime = ff_prime / 2;
25  if ( ! ff_big )
26  memset( ff_invtab, 0, ff_prime*sizeof(short) );
27  }
28 }
VAR int ff_halfprime
Definition: ffops.cc:15
VAR bool ff_big
Definition: ffops.cc:16

◆ ff_sub()

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

Definition at line 112 of file ffops.h.

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 }

◆ 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:31
INST_VAR CFSwitches cf_glob_switches
Definition: cf_switches.cc:41
bool isOn(int s) const
check if 's' is on
Definition: cf_switches.h:55
EXTERN_VAR int ff_halfprime
Definition: ffops.h:31

◆ 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

EXTERN_VAR bool ff_big

Definition at line 33 of file ffops.h.

◆ ff_halfprime

EXTERN_VAR int ff_halfprime

Definition at line 31 of file ffops.h.

◆ ff_invtab

EXTERN_VAR short* ff_invtab

Definition at line 32 of file ffops.h.

◆ ff_prime

EXTERN_VAR int ff_prime

Definition at line 30 of file ffops.h.