My Project  debian-1:4.1.1-p2+ds-4
ffops.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 
4 #include "config.h"
5 
6 
7 #include <string.h>
8 
9 #include "cf_assert.h"
10 
11 #include "cf_defs.h"
12 #include "ffops.h"
13 
14 int ff_prime = 0;
15 int ff_halfprime = 0;
16 bool ff_big = false;
17 short * ff_invtab = new short [32767];
18 
19 void ff_setprime ( const int p )
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 }
28 
29 int ff_newinv ( const int a )
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 }
70 
71 int ff_biginv ( const int a )
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 }
ff_invtab
short * ff_invtab
Definition: ffops.cc:17
cf_defs.h
ff_newinv
int ff_newinv(const int a)
Definition: ffops.cc:29
ff_prime
int ff_prime
Definition: ffops.cc:14
ff_big
bool ff_big
Definition: ffops.cc:16
cf_assert.h
p
int p
Definition: cfModGcd.cc:4019
ff_halfprime
int ff_halfprime
Definition: ffops.cc:15
ff_biginv
int ff_biginv(const int a)
Definition: ffops.cc:71
ffops.h
ff_setprime
void ff_setprime(const int p)
Definition: ffops.cc:19