1 #include "sys.h"
2 #include "debug.h"
3 #include <iostream>
4 #include <cassert>
5 #include <iomanip>
6 #include <sstream>
7 #include <libecc/point.h>
8 #include <libecc/fieldmath.h>
9 #include "utils.h"
10
11 #define VERBOSE
12
13 using std::cout;
14 using std::endl;
15 using std::flush;
16 using libecc::bitset_base;
17 using libecc::bitset_digit_t;
18
19 typedef libecc::bitset<m> bitset;
20
21 poly_t a;
22 poly_t b;
23 typedef libecc::point<poly_t, a, b> point;
24
25 // Returns the number of elements with foc n and trace 1.
tr1c(unsigned int n)26 mpz_class tr1c(unsigned int n)
27 {
28 mpz_class result = foc(n);
29 while (n % 2 == 0)
30 {
31 n /= 2;
32 result += foc(n);
33 }
34 result /= 2;
35 return result;
36 }
37
38 class F2Ring {
39 private:
40 bool M_val;
41
42 public:
F2Ring(void)43 F2Ring(void) : M_val(false) { }
F2Ring(F2Ring const & r)44 F2Ring(F2Ring const& r) : M_val(r.M_val) { }
operator =(F2Ring const & r)45 F2Ring& operator=(F2Ring const& r) { M_val = r.M_val; return *this; }
F2Ring(unsigned int constant)46 F2Ring(unsigned int constant) : M_val((constant & 1) != 0) { }
operator =(unsigned int constant)47 F2Ring& operator=(unsigned int constant) { M_val = (constant & 1) != 0; return *this; }
F2Ring(bool val)48 F2Ring(bool val) : M_val(val) { }
operator =(bool val)49 F2Ring& operator=(bool val){ M_val = val; return *this; }
operator <<(std::ostream & os,F2Ring const & r)50 friend std::ostream& operator<<(std::ostream& os, F2Ring const& r) { os << (r.M_val ? 1 : 0); return os; }
operator +=(F2Ring const & r)51 F2Ring& operator+=(F2Ring const& r) { M_val = (M_val != r.M_val); return *this; }
operator +(F2Ring const & r1,F2Ring const & r2)52 friend F2Ring operator+(F2Ring const& r1, F2Ring const& r2) { F2Ring result(r1); result += r2; return result; }
operator *(F2Ring const & r1,F2Ring const & r2)53 friend F2Ring operator*(F2Ring const& r1, F2Ring const& r2) { F2Ring result(r1.M_val && r2.M_val); return result; }
operator *=(F2Ring const & r)54 F2Ring& operator*=(F2Ring const& r) { M_val = M_val && r.M_val; return *this; }
val(void) const55 bool val(void) const { return M_val; }
operator !=(F2Ring const & r) const56 bool operator!=(F2Ring const& r) const { return M_val != r.M_val; }
operator ==(F2Ring const & r) const57 bool operator==(F2Ring const& r) const { return M_val == r.M_val; }
58 };
59
60 class SymbolicF2Ring {
61 private:
62 libecc::bitset<q> M_terms;
63
64 public:
SymbolicF2Ring(void)65 SymbolicF2Ring(void) { M_terms.reset(); }
SymbolicF2Ring(SymbolicF2Ring const & r)66 SymbolicF2Ring(SymbolicF2Ring const& r) : M_terms(r.M_terms) { }
operator =(SymbolicF2Ring const & r)67 SymbolicF2Ring& operator=(SymbolicF2Ring const& r) { M_terms = r.M_terms; return *this; }
SymbolicF2Ring(unsigned int constant)68 SymbolicF2Ring(unsigned int constant)
69 {
70 if ((constant & 1))
71 M_terms.setall();
72 else
73 M_terms.reset();
74 }
operator =(unsigned int constant)75 SymbolicF2Ring& operator=(unsigned int constant)
76 {
77 if ((constant & 1))
78 M_terms.setall();
79 else
80 M_terms.reset();
81 return *this;
82 }
SymbolicF2Ring(bitset const & factors)83 SymbolicF2Ring(bitset const& factors)
84 {
85 M_terms.reset();
86 M_terms.set(factors.digit(0));
87 }
operator =(bitset const & factors)88 SymbolicF2Ring& operator=(bitset const& factors)
89 {
90 M_terms.reset();
91 M_terms.set(factors.digit(0));
92 return *this;
93 }
94 friend std::ostream& operator<<(std::ostream& os, SymbolicF2Ring const& r);
operator +=(SymbolicF2Ring const & r)95 SymbolicF2Ring& operator+=(SymbolicF2Ring const& r)
96 {
97 M_terms ^= r.M_terms;
98 return *this;
99 }
operator +(SymbolicF2Ring const & r1,SymbolicF2Ring const & r2)100 friend SymbolicF2Ring operator+(SymbolicF2Ring const& r1, SymbolicF2Ring const& r2)
101 { SymbolicF2Ring result(r1); result += r2; return result; }
102 friend SymbolicF2Ring operator*(SymbolicF2Ring const& r1, SymbolicF2Ring const& r2);
operator *=(SymbolicF2Ring const & r)103 SymbolicF2Ring& operator*=(SymbolicF2Ring const& r)
104 { SymbolicF2Ring tmp(*this); *this = tmp * r; return *this; }
terms(void) const105 libecc::bitset<q> const& terms(void) const {return M_terms; }
106 };
107
operator *(SymbolicF2Ring const & r1,SymbolicF2Ring const & r2)108 SymbolicF2Ring operator*(SymbolicF2Ring const& r1, SymbolicF2Ring const& r2)
109 {
110 SymbolicF2Ring result;
111 libecc::bitset<q>::const_iterator iter1 = r1.M_terms.begin();
112 for (++iter1, iter1.find1(); iter1 != r1.M_terms.end(); ++iter1, iter1.find1())
113 {
114 libecc::bitset<q>::const_iterator iter2 = r2.M_terms.begin();
115 for (++iter2, iter2.find1(); iter2 != r2.M_terms.end(); ++iter2, iter2.find1())
116 result.M_terms.flip(iter1.get_index() | iter2.get_index());
117 }
118 return result;
119 }
120
operator <<(std::ostream & os,SymbolicF2Ring const & r2)121 std::ostream& operator<<(std::ostream& os, SymbolicF2Ring const& r2)
122 {
123 SymbolicF2Ring r(r2);
124 bool all_zeroes = (r.M_terms.digit(libecc::bitset<q>::digits - 1) & ~((libecc::bitset<q>::digits == 1) ? 1 : 0)) == 0;
125 bool all_ones = (r.M_terms.digit(libecc::bitset<q>::digits - 1) | ((libecc::bitset<q>::digits == 1) ? 1 : 0)) == libecc::bitset<q>::valid_bits;
126 for (int d = libecc::bitset<q>::digits - 2; d >= 0 && (all_zeroes || all_ones); --d)
127 {
128 if (r.M_terms.digit(d) != 0 && (d > 0 || r.M_terms.digit(d) != 1))
129 all_zeroes = false;
130 if (r.M_terms.digit(d) != 0xffffffff && (d > 0 || r.M_terms.digit(d) != 0xfffffffe))
131 all_ones = false;
132 }
133 if (all_zeroes)
134 os << '0';
135 else if (all_ones)
136 os << '1';
137 else
138 {
139 bool first = true;
140 libecc::bitset<q>::const_iterator iter = r.M_terms.begin();
141 for (++iter, iter.find1(); iter != r.M_terms.end(); ++iter, iter.find1())
142 {
143 if (!first)
144 os << "+";
145 bitset product(iter.get_index());
146 for (unsigned int bit = 0; bit < m; ++bit)
147 {
148 if (product.test(bit))
149 os << (char)('a' + bit);
150 }
151 first = false;
152 }
153 }
154 return os;
155 }
156
157 template<typename T>
158 class Vector {
159 private:
160 T M_elements[m];
161 public:
Vector(void)162 Vector(void) { }
Vector(Vector const & v)163 Vector(Vector const& v) : M_elements(v.M_elements) { }
operator =(Vector const & v)164 Vector& operator=(Vector const& v) { for (unsigned int i = 0; i < m; ++i) M_elements[i] = v.M_elements[i]; return *this; }
operator [](unsigned int index)165 T& operator[](unsigned int index) { return M_elements[index]; }
operator [](unsigned int index) const166 T const& operator[](unsigned int index) const { return M_elements[index]; }
167 template<typename T2>
168 friend std::ostream& operator<<(std::ostream& os, Vector<T2> const& v);
169 template<typename T2>
170 friend T2 operator*(Vector<T2> const& v1, Vector<T2> const& v2);
operator +=(Vector const & v)171 Vector& operator+=(Vector const& v) { for (unsigned int i = 0; i < m; ++i) M_elements[i] += v.M_elements[i]; return *this; }
172 T trace(void) const;
operator !=(Vector const & v) const173 bool operator!=(Vector const& v) const
174 {
175 for (unsigned int i = 0; i < m; ++i)
176 if (M_elements[i] != v.M_elements[i])
177 return true;
178 return false;
179 }
operator ==(Vector const & v) const180 bool operator==(Vector const& v) const { return !this->operator!=(v); }
181 };
182
183 template<typename T>
trace(void) const184 T Vector<T>::trace(void) const
185 {
186 T result;
187 if ((m & 1))
188 result = M_elements[0];
189 if (((m - k) & 1))
190 result += M_elements[m - k];
191 if (k1 && ((m - k1) & 1))
192 result += M_elements[m - k1];
193 if (k2 && ((m - k2) & 1))
194 result += M_elements[m - k2];
195 return result;
196 }
197
198 template<typename T>
operator *(Vector<T> const & v1,Vector<T> const & v2)199 T operator*(Vector<T> const& v1, Vector<T> const& v2)
200 {
201 T result(v1[0] * v2[0]);
202 for (unsigned int i = 1; i < m; ++i)
203 result += v1[i] * v2[i];
204 return result;
205 }
206
207 template<typename T>
operator <<(std::ostream & os,Vector<T> const & v)208 std::ostream& operator<<(std::ostream& os, Vector<T> const& v)
209 {
210 os << '(' << v.M_elements[0];
211 for (unsigned int i = 1; i < m; ++i)
212 {
213 os << ", " << v.M_elements[i];
214 }
215 os << ")^T";
216 return os;
217 }
218
219 template<typename T>
220 class Matrix {
221 private:
222 Vector<T> M_columns[m];
223 static Matrix S_unity;
224 public:
Matrix(void)225 Matrix(void) { }
Matrix(Matrix const & matrix)226 Matrix(Matrix const& matrix) : M_columns(matrix.M_columns) { }
operator =(Matrix const & matrix)227 Matrix& operator=(Matrix const& matrix) { for (unsigned int col = 0; col < m; ++col) M_columns[col] = matrix.M_columns[col]; return *this; }
228 Matrix(Vector<T> const& v);
operator [](unsigned int column)229 Vector<T>& operator[](unsigned int column) { return M_columns[column]; }
operator [](unsigned int column) const230 Vector<T> const& operator[](unsigned int column) const { return M_columns[column]; }
row(unsigned int row)231 Vector<T> row(unsigned int row)
232 { Vector<T> result; for (unsigned int col = 0; col < m; ++col) result[col] = M_columns[col][row]; return result; }
element(unsigned int row,unsigned int col)233 T& element(unsigned int row, unsigned int col) { return M_columns[col][row]; }
element(unsigned int row,unsigned int col) const234 T const& element(unsigned int row, unsigned int col) const { return M_columns[col][row]; }
235 template<typename T2>
236 friend std::ostream& operator<<(std::ostream& os, Matrix<T2> const& matrix);
237 Vector<T> operator*(Vector<T> const& v) const;
238 template<typename T2>
239 friend Matrix<T2> operator*(Matrix<T2> const& m1, Matrix<T2> const& m2);
operator *=(Matrix<T> const & m1)240 Matrix<T>& operator*=(Matrix<T> const& m1) { Matrix<T> tmp = *this * m1; return (*this = tmp); }
241 T trace(void);
242 void invert(void);
Matrix(unsigned int)243 Matrix(unsigned int) { for (unsigned int i = 0; i < m; ++i) M_columns[i][i] = 1U; }
unity(void)244 static Matrix const& unity(void) { return S_unity; }
operator !=(Matrix const & matrix) const245 bool operator!=(Matrix const& matrix) const
246 {
247 for (unsigned int i = 0; i < m; ++i)
248 if (M_columns[i] != matrix.M_columns[i])
249 return true;
250 return false;
251 }
operator ==(Matrix const & matrix) const252 bool operator==(Matrix const& matrix) const { return !this->operator!=(matrix); }
253 };
254
255 template<typename T>
256 Matrix<T> Matrix<T>::S_unity(1U);
257
258 template<typename T>
259 void
invert(void)260 Matrix<T>::invert(void)
261 {
262 Matrix<T> result;
263 Matrix<T> tmp(*this);
264 do
265 {
266 result = tmp;
267 tmp *= *this;
268 }
269 while (tmp != unity());
270 *this = result;
271 }
272
273 template<typename T>
trace(void)274 T Matrix<T>::trace(void)
275 {
276 T result(M_columns[0][0]);
277 for (unsigned int i = 1; i < m; ++i)
278 result += M_columns[i][i];
279 return result;
280 }
281
282 template<typename T>
Matrix(Vector<T> const & v)283 Matrix<T>::Matrix(Vector<T> const& v)
284 {
285 M_columns[0] = v;
286 for (unsigned int i = 1; i < m; ++i)
287 {
288 for (unsigned int j = 1; j < m; ++j)
289 M_columns[i][j] = M_columns[i - 1][j - 1];
290 M_columns[i][0] = M_columns[i - 1][m - 1];
291 M_columns[i][k] += M_columns[i - 1][m - 1];
292 if (k1)
293 {
294 M_columns[i][k1] += M_columns[i - 1][m - 1];
295 M_columns[i][k2] += M_columns[i - 1][m - 1];
296 }
297 }
298 }
299
300 template<typename T>
operator *(Matrix<T> const & m1,Matrix<T> const & m2)301 Matrix<T> operator*(Matrix<T> const& m1, Matrix<T> const& m2)
302 {
303 Matrix<T> result;
304 for (unsigned int col = 0; col < m; ++col)
305 {
306 for (unsigned int i = 0; i < m; ++i)
307 {
308 result.M_columns[col][i] = m2.M_columns[col][0] * m1.M_columns[0][i];
309 for (unsigned int j = 1; j < m; ++j)
310 result.M_columns[col][i] += m2.M_columns[col][j] * m1.M_columns[j][i];
311 }
312 }
313 return result;
314 }
315
316 template<typename T>
operator *(Vector<T> const & v) const317 Vector<T> Matrix<T>::operator*(Vector<T> const& v) const
318 {
319 Vector<T> result;
320 for (unsigned int i = 0; i < m; ++i)
321 {
322 result[i] = v[0] * M_columns[0][i];
323 for (unsigned int j = 1; j < m; ++j)
324 result[i] += v[j] * M_columns[j][i];
325 }
326 return result;
327 }
328
329 template<typename T>
operator <<(std::ostream & os,Matrix<T> const & matrix)330 std::ostream& operator<<(std::ostream& os, Matrix<T> const& matrix)
331 {
332 size_t max_width[m];
333 for (unsigned int col = 0; col < m; ++col)
334 {
335 max_width[col] = 0;
336 for (unsigned int row = 0; row < m; ++row)
337 {
338 std::ostringstream buf;
339 buf << ' ' << matrix.M_columns[col][row];
340 if (buf.str().length() > max_width[col])
341 max_width[col] = buf.str().length();
342 }
343 }
344 for (unsigned int row = 0; row < m; ++row)
345 {
346 os << "|";
347 for (unsigned int col = 0; col < m; ++col)
348 {
349 std::ostringstream buf;
350 buf << ' ' << matrix.M_columns[col][row];
351 os << std::setw(max_width[col]) << buf.str() << " |";
352 }
353 os << endl;
354 }
355 return os;
356 }
357
main()358 int main()
359 {
360 initialize_utils();
361
362 libecc::bitset<q> h;
363 h.reset();
364 for (unsigned int n = 1; n <= m; ++n)
365 {
366 int nn = 0;
367 for (unsigned int v = 0; v < q; ++v)
368 {
369 if (h.test(v))
370 continue;
371 unsigned int mask = q >> 1;
372 unsigned int count = 0;
373 while(mask)
374 {
375 if ((mask & v))
376 ++count;
377 mask >>= 1;
378 }
379 if (count != n)
380 continue;
381 cout << poly_t(v) << endl;
382 ++nn;
383 bitset p(v), result;
384 for (unsigned int i = 0; i < m; ++i)
385 {
386 h.set(p.digit(0));
387 p.rotate<1, libecc::left>(result);
388 p = result;
389 }
390 }
391 cout << nn << " patterns with " << n << " bits set." << endl;
392 }
393
394 #ifdef VERBOSE
395 cout << "The cardinality of the field (q) is " << q << " (m = " << m << ")." << endl;
396 cout << "n = " << poly_t(poly_t::normal()) << endl;
397 #endif
398
399 poly_t nb[m];
400 for (bitset_digit_t v = 1; v < q; ++v)
401 {
402 poly_t g(v);
403 if (g.trace() == 0)
404 continue;
405 // Try to create the normal basis.
406 nb[0] = g;
407 unsigned int i;
408 for (i = 1; i < m; ++i)
409 {
410 nb[i] = nb[i - 1] * nb[i - 1];
411 if (nb[i].get_bitset().digit(0) < v)
412 break;
413 if (nb[i] == g)
414 break;
415 }
416 if (i != m)
417 continue;
418 libecc::bitset<q> h;
419 h.reset();
420 bitset_digit_t v2;
421 for (v2 = 0; v2 < q; ++v2)
422 {
423 bitset b2(v2);
424 poly_t x(0);
425 for (unsigned int i = 0; i < m; ++i)
426 {
427 if (b2.test(i))
428 x += nb[i];
429 }
430 if (h.test(x.get_bitset().digit(0)))
431 break;
432 h.set(x.get_bitset().digit(0));
433 }
434 if (v2 != q)
435 continue;
436 cout << "Found normal basis = { " << nb[0];
437 for (unsigned int i = 1; i < m; ++i)
438 cout << ", " << nb[i];
439 cout << " }" << endl;
440
441 poly_t x(g);
442 unsigned int n;
443 for (n = 1; n < q; ++n)
444 {
445 x *= g; // x = g^(n + 1)
446 if (x == g)
447 break;
448 }
449 assert((q - 1) % n == 0);
450 cout << "g^((q - 1)/" << ((q - 1) / n) << ") = 1" << endl;
451
452 Matrix<F2Ring> M_b;
453 for (unsigned int col = 0; col < m; ++col)
454 for (unsigned int row = 0; row < m; ++row)
455 M_b[col][row] = nb[col].get_bitset().test(row);
456
457 //cout << "M_b = \n" << M_b << endl;
458 Matrix<F2Ring> M_b_inv(M_b);
459 M_b_inv.invert();
460 //cout << "M_b^(-1) = \n" << M_b_inv << endl;
461
462 Matrix<SymbolicF2Ring> M_n2t;
463 Matrix<SymbolicF2Ring> M_t2n;
464 for (unsigned int col = 0; col < m; ++col)
465 {
466 for (unsigned int row = 0; row < m; ++row)
467 {
468 M_n2t[col][row] = M_b[col][row].val() ? 1U : 0U;
469 M_t2n[col][row] = M_b_inv[col][row].val() ? 1U : 0U;
470 }
471 }
472 // cout << "M_n2t = \n" << M_n2t << endl;
473 // cout << "M_t2n = \n" << M_t2n << endl;
474
475 // Define an _arbitrary_ vector.
476 Vector<SymbolicF2Ring> v;
477 for (unsigned int i = 0; i < m; ++i)
478 v[i] = bitset(1 << i); // Each variable is represented by a different bit.
479 // Thus, this way we assign a different variable to each bit.
480
481 if (0)
482 {
483 // Limit this vector to those vectors for which Tr(v) = 0.
484 // The trace is the sum of each set bit in the normal.
485 bitset::const_iterator iter = poly_t::normal().begin();
486 // Find the first bit that is set, this is the variable that we will replace with the other bits.
487 // For example, if Tr(x) = Tr(c_x t^x + c_y t^y + c_z t^z) then we set c_x = c_y + c_z by
488 // adding 'cx + cy + c_z' to the place in the vector that now holds c_x.
489 iter.find1();
490 int eliminated_variable = iter.get_index();
491 // Eliminate the variable that corresponds to that bit.
492 do
493 {
494 v[eliminated_variable] += SymbolicF2Ring(bitset(1 << iter.get_index()));
495 ++iter;
496 iter.find1();
497 }
498 while(iter != poly_t::normal().end());
499 }
500
501 // cout << "v = " << v << endl;
502 // cout << "M_n2t v = " << (M_n2t * v) << endl;
503
504 Matrix<SymbolicF2Ring> M_v(M_n2t * v); // Create the matrix corresponding with this vector.
505
506 // cout << "M_v = \n" << M_v << endl;
507
508 M_v = M_t2n * (M_v * M_n2t);
509
510 // cout << "M_t2n * M_v * M_n2t = \n" << M_v << endl;
511
512 Matrix<SymbolicF2Ring> M2n[m];
513 M2n[0] = M_v;
514 for (unsigned int i = 1; i < m; ++i)
515 M2n[i] = M2n[i - 1] * M2n[i - 1]; // Calculate M_v^(2^n)
516 Matrix<SymbolicF2Ring> M_v_inverse(M2n[1]);
517 for (unsigned int i = 2; i < m; ++i)
518 M_v_inverse *= M2n[i]; // Calculate M_v^(2^1) * M_v^(2^2) * ... * M_v^(2^(m-1)) = M_v^(2^m - 2) = M_v^(-1).
519
520 // cout << "M_v^(-1) = \n" << M_v_inverse << endl;
521
522 Vector<SymbolicF2Ring> v_inverse = M_v_inverse[0];
523 for (unsigned int i = 1; i < m; ++i)
524 v_inverse += M_v_inverse[i];
525 cout << "v^(-1) = " << v_inverse << " (normal basis)" << endl;
526
527 #if 0
528 cout << "Tr(v) = " << (M_n2t * v).trace() << endl;
529 cout << "Tr(M_v) = " << M_v.trace() << endl;
530 cout << "Tr(v^-1) = " << (M_n2t * v_inverse).trace() << endl;
531 cout << "Tr(M_v^(-1)) = " << M_v_inverse.trace() << endl;
532 #endif
533
534 cout << "Tr(v + v^-1) = ";
535 libecc::bitset<q> terms2((M_v.trace() + M_v_inverse.trace()).terms());
536 bool first_time = true;
537 for (unsigned int number_of_bits_in_pattern = 1; number_of_bits_in_pattern <= m; ++number_of_bits_in_pattern)
538 {
539 //cout << "number_of_bits_in_pattern = " << number_of_bits_in_pattern << endl;
540 for (bitset_digit_t pattern = 1; pattern < q; ++pattern)
541 {
542 unsigned int bit_count = 0;
543 for (bitset_digit_t mask = 1; mask < q; mask <<= 1)
544 if ((pattern & mask))
545 ++bit_count;
546 if (bit_count != number_of_bits_in_pattern)
547 continue;
548 //cout << "pattern = " << poly_t(pattern) << endl;
549 if (terms2.test(pattern))
550 {
551 //cout << "pattern is set in M_terms" << endl;
552 bitset product(pattern);
553 bitset rotate_result;
554 bitset_digit_t min_pattern = pattern;
555 for (unsigned int shift = 1; shift < m; ++shift)
556 {
557 product.rotate<1, libecc::left>(rotate_result);
558 product = rotate_result;
559 if (product.digit(0) < min_pattern)
560 min_pattern = product.digit(0);
561 //cout << "Rotated pattern is " << poly_t(product) << endl;
562 assert(terms2.test(product.digit(0)));
563 terms2.clear(product.digit(0));
564 //cout << "Cleared pattern " << poly_t(product) << endl;
565 if (product.digit(0) == 0 || product.digit(0) == q - 1)
566 break;
567 }
568 if (!first_time)
569 cout << " + ";
570 else
571 {
572 cout << "\n ";
573 first_time = false;
574 }
575 cout << "C_" << number_of_bits_in_pattern << "(" << poly_t(min_pattern) << ")" << endl;
576 }
577 }
578 }
579 cout << endl;
580
581 // Next, count the non-zero number of elements for which Tr(v + v^1) is 0.
582 // Create a list of all non-zero product terms.
583 std::vector<bitset> products;
584 libecc::bitset<q> const terms((M_v.trace() + M_v_inverse.trace()).terms());
585 libecc::bitset<q>::const_iterator iter = terms.begin();
586 ++iter; // The first bit is nonsense.
587 for (iter.find1(); iter != terms.end(); ++iter, iter.find1())
588 products.push_back(bitset(iter.get_index()));
589 unsigned int count = 0;
590 for (unsigned int v = 1; v < q; ++v)
591 {
592 unsigned int trace = 0;
593 // Find all product terms that are 1.
594 for (std::vector<bitset>::iterator iter = products.begin(); iter != products.end(); ++iter)
595 if ((v & iter->digit(0)) == iter->digit(0))
596 trace ^= 1;
597 //cout << "Tr(" << poly_t(v) << ") = " << trace << endl;
598 if (trace == 0)
599 ++count;
600 }
601 cout << "Count = " << count << endl;
602 }
603
604 return 0;
605 }
606