Botan  2.19.1
Crypto and TLS for C++11
gf2m_small_m.h
Go to the documentation of this file.
1 /*
2  * (C) Copyright Projet SECRET, INRIA, Rocquencourt
3  * (C) Bhaskar Biswas and Nicolas Sendrier
4  *
5  * (C) 2014 cryptosource GmbH
6  * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
7  *
8  * Botan is released under the Simplified BSD License (see license.txt)
9  *
10  */
11 
12 #ifndef BOTAN_GF2M_SMALL_M_H_
13 #define BOTAN_GF2M_SMALL_M_H_
14 
15 #include <botan/types.h>
16 #include <vector>
17 
18 BOTAN_FUTURE_INTERNAL_HEADER(gf2m_small_m.h)
19 
20 namespace Botan {
21 
22 typedef uint16_t gf2m;
23 
24 /**
25 * GF(2^m) field for m = [2...16]
26 */
28  {
29  public:
30  explicit GF2m_Field(size_t extdeg);
31 
32  gf2m gf_mul(gf2m x, gf2m y) const
33  {
34  return ((x) ? gf_mul_fast(x, y) : 0);
35  }
36 
37  gf2m gf_square(gf2m x) const
38  {
39  return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << 1)) : 0);
40  }
41 
42  gf2m square_rr(gf2m x) const
43  {
44  return _gf_modq_1(x << 1);
45  }
46 
47  gf2m gf_mul_fast(gf2m x, gf2m y) const
48  {
49  return ((y) ? gf_exp(_gf_modq_1(gf_log(x) + gf_log(y))) : 0);
50  }
51 
52  /*
53  naming convention of GF(2^m) field operations:
54  l logarithmic, unreduced
55  r logarithmic, reduced
56  n normal, non-zero
57  z normal, might be zero
58  */
59 
60  gf2m gf_mul_lll(gf2m a, gf2m b) const
61  {
62  return (a + b);
63  }
64 
65  gf2m gf_mul_rrr(gf2m a, gf2m b) const
66  {
67  return (_gf_modq_1(gf_mul_lll(a, b)));
68  }
69 
70  gf2m gf_mul_nrr(gf2m a, gf2m b) const
71  {
72  return (gf_exp(gf_mul_rrr(a, b)));
73  }
74 
75  gf2m gf_mul_rrn(gf2m a, gf2m y) const
76  {
77  return _gf_modq_1(gf_mul_lll(a, gf_log(y)));
78  }
79 
80  gf2m gf_mul_rnr(gf2m y, gf2m a) const
81  {
82  return gf_mul_rrn(a, y);
83  }
84 
85  gf2m gf_mul_lnn(gf2m x, gf2m y) const
86  {
87  return (gf_log(x) + gf_log(y));
88  }
89 
90  gf2m gf_mul_rnn(gf2m x, gf2m y) const
91  {
92  return _gf_modq_1(gf_mul_lnn(x, y));
93  }
94 
95  gf2m gf_mul_nrn(gf2m a, gf2m y) const
96  {
97  return gf_exp(_gf_modq_1((a) + gf_log(y)));
98  }
99 
100  /**
101  * zero operand allowed
102  */
103  gf2m gf_mul_zrz(gf2m a, gf2m y) const
104  {
105  return ( (y == 0) ? 0 : gf_mul_nrn(a, y) );
106  }
107 
108  gf2m gf_mul_zzr(gf2m a, gf2m y) const
109  {
110  return gf_mul_zrz(y, a);
111  }
112 
113  /**
114  * non-zero operand
115  */
116  gf2m gf_mul_nnr(gf2m y, gf2m a) const
117  {
118  return gf_mul_nrn(a, y);
119  }
120 
121  gf2m gf_sqrt(gf2m x) const
122  {
123  return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << (get_extension_degree()-1))) : 0);
124  }
125 
126  gf2m gf_div_rnn(gf2m x, gf2m y) const
127  {
128  return _gf_modq_1(gf_log(x) - gf_log(y));
129  }
130 
131  gf2m gf_div_rnr(gf2m x, gf2m b) const
132  {
133  return _gf_modq_1(gf_log(x) - b);
134  }
135 
136  gf2m gf_div_nrr(gf2m a, gf2m b) const
137  {
138  return gf_exp(_gf_modq_1(a - b));
139  }
140 
141  gf2m gf_div_zzr(gf2m x, gf2m b) const
142  {
143  return ((x) ? gf_exp(_gf_modq_1(gf_log(x) - b)) : 0);
144  }
145 
146  gf2m gf_inv(gf2m x) const
147  {
148  return gf_exp(gf_ord() - gf_log(x));
149  }
150 
151  gf2m gf_inv_rn(gf2m x) const
152  {
153  return (gf_ord() - gf_log(x));
154  }
155 
156  gf2m gf_square_ln(gf2m x) const
157  {
158  return gf_log(x) << 1;
159  }
160 
161  gf2m gf_square_rr(gf2m a) const
162  {
163  return a << 1;
164  }
165 
166  gf2m gf_l_from_n(gf2m x) const
167  {
168  return gf_log(x);
169  }
170 
171  gf2m gf_div(gf2m x, gf2m y) const;
172 
173  gf2m gf_exp(gf2m i) const
174  {
175  return m_gf_exp_table.at(i); /* alpha^i */
176  }
177 
178  gf2m gf_log(gf2m i) const
179  {
180  return m_gf_log_table.at(i); /* return i when x=alpha^i */
181  }
182 
183  gf2m gf_ord() const
184  {
185  return m_gf_multiplicative_order;
186  }
187 
188  size_t get_extension_degree() const
189  {
190  return m_gf_extension_degree;
191  }
192 
193  gf2m get_cardinality() const
194  {
195  return static_cast<gf2m>(1 << get_extension_degree());
196  }
197 
198  private:
199  gf2m _gf_modq_1(int32_t d) const
200  {
201  /* residual modulo q-1
202  when -q < d < 0, we get (q-1+d)
203  when 0 <= d < q, we get (d)
204  when q <= d < 2q-1, we get (d-q+1)
205  */
206  return static_cast<gf2m>(((d) & gf_ord()) + ((d) >> get_extension_degree()));
207  }
208 
209  const size_t m_gf_extension_degree;
210  const gf2m m_gf_multiplicative_order;
211  const std::vector<gf2m>& m_gf_log_table;
212  const std::vector<gf2m>& m_gf_exp_table;
213  };
214 
215 uint32_t encode_gf2m(gf2m to_enc, uint8_t* mem);
216 
217 gf2m decode_gf2m(const uint8_t* mem);
218 
219 }
220 
221 #endif
gf2m gf_inv_rn(gf2m x) const
Definition: gf2m_small_m.h:151
gf2m get_cardinality() const
Definition: gf2m_small_m.h:193
gf2m gf_mul(gf2m x, gf2m y) const
Definition: gf2m_small_m.h:32
gf2m gf_mul_zzr(gf2m a, gf2m y) const
Definition: gf2m_small_m.h:108
gf2m gf_square(gf2m x) const
Definition: gf2m_small_m.h:37
gf2m gf_mul_lnn(gf2m x, gf2m y) const
Definition: gf2m_small_m.h:85
gf2m gf_mul_rnn(gf2m x, gf2m y) const
Definition: gf2m_small_m.h:90
gf2m decode_gf2m(const uint8_t *mem)
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:31
gf2m gf_mul_rnr(gf2m y, gf2m a) const
Definition: gf2m_small_m.h:80
gf2m gf_mul_fast(gf2m x, gf2m y) const
Definition: gf2m_small_m.h:47
gf2m gf_mul_lll(gf2m a, gf2m b) const
Definition: gf2m_small_m.h:60
gf2m gf_mul_rrn(gf2m a, gf2m y) const
Definition: gf2m_small_m.h:75
gf2m gf_div_rnn(gf2m x, gf2m y) const
Definition: gf2m_small_m.h:126
gf2m gf_square_rr(gf2m a) const
Definition: gf2m_small_m.h:161
gf2m gf_inv(gf2m x) const
Definition: gf2m_small_m.h:146
gf2m gf_log(gf2m i) const
Definition: gf2m_small_m.h:178
gf2m gf_mul_nrr(gf2m a, gf2m b) const
Definition: gf2m_small_m.h:70
gf2m gf_mul_nrn(gf2m a, gf2m y) const
Definition: gf2m_small_m.h:95
uint16_t gf2m
Definition: gf2m_small_m.h:22
Definition: alg_id.cpp:13
gf2m gf_l_from_n(gf2m x) const
Definition: gf2m_small_m.h:166
gf2m gf_mul_nnr(gf2m y, gf2m a) const
Definition: gf2m_small_m.h:116
uint32_t encode_gf2m(gf2m to_enc, uint8_t *mem)
gf2m gf_mul_zrz(gf2m a, gf2m y) const
Definition: gf2m_small_m.h:103
size_t get_extension_degree() const
Definition: gf2m_small_m.h:188
gf2m gf_square_ln(gf2m x) const
Definition: gf2m_small_m.h:156
gf2m gf_ord() const
Definition: gf2m_small_m.h:183
gf2m gf_sqrt(gf2m x) const
Definition: gf2m_small_m.h:121
gf2m gf_exp(gf2m i) const
Definition: gf2m_small_m.h:173
gf2m gf_mul_rrr(gf2m a, gf2m b) const
Definition: gf2m_small_m.h:65
gf2m square_rr(gf2m x) const
Definition: gf2m_small_m.h:42
gf2m gf_div_nrr(gf2m a, gf2m b) const
Definition: gf2m_small_m.h:136
gf2m gf_div_rnr(gf2m x, gf2m b) const
Definition: gf2m_small_m.h:131
#define BOTAN_FUTURE_INTERNAL_HEADER(hdr)
Definition: compiler.h:136
gf2m gf_div_zzr(gf2m x, gf2m b) const
Definition: gf2m_small_m.h:141