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