Botan  2.4.0
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 <vector>
16 #include <botan/types.h>
17 
18 namespace Botan {
19 
20 typedef uint16_t gf2m;
21 
22 /**
23 * GF(2^m) field for m = [2...16]
24 */
26  {
27  public:
28  explicit GF2m_Field(size_t extdeg);
29 
30  gf2m gf_mul(gf2m x, gf2m y) const
31  {
32  return ((x) ? gf_mul_fast(x, y) : 0);
33  }
34 
35  gf2m gf_square(gf2m x) const
36  {
37  return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << 1)) : 0);
38  }
39 
40  gf2m square_rr(gf2m x) const
41  {
42  return _gf_modq_1(x << 1);
43  }
44 
45  gf2m gf_mul_fast(gf2m x, gf2m y) const
46  {
47  return ((y) ? gf_exp(_gf_modq_1(gf_log(x) + gf_log(y))) : 0);
48  }
49 
50  /*
51  naming convention of GF(2^m) field operations:
52  l logarithmic, unreduced
53  r logarithmic, reduced
54  n normal, non-zero
55  z normal, might be zero
56  */
57 
58  gf2m gf_mul_lll(gf2m a, gf2m b) const
59  {
60  return (a + b);
61  }
62 
63  gf2m gf_mul_rrr(gf2m a, gf2m b) const
64  {
65  return (_gf_modq_1(gf_mul_lll(a, b)));
66  }
67 
68  gf2m gf_mul_nrr(gf2m a, gf2m b) const
69  {
70  return (gf_exp(gf_mul_rrr(a, b)));
71  }
72 
73  gf2m gf_mul_rrn(gf2m a, gf2m y) const
74  {
75  return _gf_modq_1(gf_mul_lll(a, gf_log(y)));
76  }
77 
78  gf2m gf_mul_rnr(gf2m y, gf2m a) const
79  {
80  return gf_mul_rrn(a, y);
81  }
82 
83  gf2m gf_mul_lnn(gf2m x, gf2m y) const
84  {
85  return (gf_log(x) + gf_log(y));
86  }
87 
88  gf2m gf_mul_rnn(gf2m x, gf2m y) const
89  {
90  return _gf_modq_1(gf_mul_lnn(x, y));
91  }
92 
93  gf2m gf_mul_nrn(gf2m a, gf2m y) const
94  {
95  return gf_exp(_gf_modq_1((a) + gf_log(y)));
96  }
97 
98  /**
99  * zero operand allowed
100  */
101  gf2m gf_mul_zrz(gf2m a, gf2m y) const
102  {
103  return ( (y == 0) ? 0 : gf_mul_nrn(a, y) );
104  }
105 
106  gf2m gf_mul_zzr(gf2m a, gf2m y) const
107  {
108  return gf_mul_zrz(y, a);
109  }
110 
111  /**
112  * non-zero operand
113  */
114  gf2m gf_mul_nnr(gf2m y, gf2m a) const
115  {
116  return gf_mul_nrn(a, y);
117  }
118 
119  gf2m gf_sqrt(gf2m x) const
120  {
121  return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << (get_extension_degree()-1))) : 0);
122  }
123 
124  gf2m gf_div_rnn(gf2m x, gf2m y) const
125  {
126  return _gf_modq_1(gf_log(x) - gf_log(y));
127  }
128 
129  gf2m gf_div_rnr(gf2m x, gf2m b) const
130  {
131  return _gf_modq_1(gf_log(x) - b);
132  }
133 
134  gf2m gf_div_nrr(gf2m a, gf2m b) const
135  {
136  return gf_exp(_gf_modq_1(a - b));
137  }
138 
139  gf2m gf_div_zzr(gf2m x, gf2m b) const
140  {
141  return ((x) ? gf_exp(_gf_modq_1(gf_log(x) - b)) : 0);
142  }
143 
144  gf2m gf_inv(gf2m x) const
145  {
146  return gf_exp(gf_ord() - gf_log(x));
147  }
148 
149  gf2m gf_inv_rn(gf2m x) const
150  {
151  return (gf_ord() - gf_log(x));
152  }
153 
154  gf2m gf_square_ln(gf2m x) const
155  {
156  return gf_log(x) << 1;
157  }
158 
159  gf2m gf_square_rr(gf2m a) const
160  {
161  return a << 1;
162  }
163 
164  gf2m gf_l_from_n(gf2m x) const
165  {
166  return gf_log(x);
167  }
168 
169  gf2m gf_div(gf2m x, gf2m y) const;
170 
171  gf2m gf_pow(gf2m x, int i) 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  gf2m 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  gf2m m_gf_extension_degree, m_gf_multiplicative_order;
210  const std::vector<gf2m>& m_gf_log_table;
211  const std::vector<gf2m>& m_gf_exp_table;
212  };
213 
214 uint32_t encode_gf2m(gf2m to_enc, uint8_t* mem);
215 
216 gf2m decode_gf2m(const uint8_t* mem);
217 
218 }
219 
220 #endif
gf2m gf_square(gf2m x) const
Definition: gf2m_small_m.h:35
gf2m gf_exp(gf2m i) const
Definition: gf2m_small_m.h:173
gf2m gf_mul_nrn(gf2m a, gf2m y) const
Definition: gf2m_small_m.h:93
gf2m gf_ord() const
Definition: gf2m_small_m.h:183
gf2m gf_square_rr(gf2m a) const
Definition: gf2m_small_m.h:159
gf2m gf_mul_lnn(gf2m x, gf2m y) const
Definition: gf2m_small_m.h:83
gf2m gf_div_rnr(gf2m x, gf2m b) const
Definition: gf2m_small_m.h:129
gf2m decode_gf2m(const uint8_t *mem)
gf2m gf_inv(gf2m x) const
Definition: gf2m_small_m.h:144
#define BOTAN_PUBLIC_API(maj, min)
Definition: compiler.h:27
gf2m gf_inv_rn(gf2m x) const
Definition: gf2m_small_m.h:149
gf2m gf_mul_nnr(gf2m y, gf2m a) const
Definition: gf2m_small_m.h:114
gf2m gf_mul_nrr(gf2m a, gf2m b) const
Definition: gf2m_small_m.h:68
gf2m gf_l_from_n(gf2m x) const
Definition: gf2m_small_m.h:164
gf2m gf_mul_rrr(gf2m a, gf2m b) const
Definition: gf2m_small_m.h:63
gf2m gf_mul(gf2m x, gf2m y) const
Definition: gf2m_small_m.h:30
gf2m gf_div_zzr(gf2m x, gf2m b) const
Definition: gf2m_small_m.h:139
gf2m gf_log(gf2m i) const
Definition: gf2m_small_m.h:178
gf2m gf_mul_rnn(gf2m x, gf2m y) const
Definition: gf2m_small_m.h:88
gf2m gf_square_ln(gf2m x) const
Definition: gf2m_small_m.h:154
gf2m get_cardinality() const
Definition: gf2m_small_m.h:193
gf2m gf_div_rnn(gf2m x, gf2m y) const
Definition: gf2m_small_m.h:124
gf2m gf_mul_rnr(gf2m y, gf2m a) const
Definition: gf2m_small_m.h:78
uint16_t gf2m
Definition: gf2m_small_m.h:20
Definition: alg_id.cpp:13
uint32_t encode_gf2m(gf2m to_enc, uint8_t *mem)
gf2m gf_mul_lll(gf2m a, gf2m b) const
Definition: gf2m_small_m.h:58
gf2m gf_div_nrr(gf2m a, gf2m b) const
Definition: gf2m_small_m.h:134
gf2m gf_mul_zrz(gf2m a, gf2m y) const
Definition: gf2m_small_m.h:101
gf2m gf_mul_zzr(gf2m a, gf2m y) const
Definition: gf2m_small_m.h:106
gf2m get_extension_degree() const
Definition: gf2m_small_m.h:188
gf2m gf_sqrt(gf2m x) const
Definition: gf2m_small_m.h:119
gf2m gf_mul_fast(gf2m x, gf2m y) const
Definition: gf2m_small_m.h:45
gf2m gf_mul_rrn(gf2m a, gf2m y) const
Definition: gf2m_small_m.h:73
gf2m square_rr(gf2m x) const
Definition: gf2m_small_m.h:40