1
2 #include "bpol/normalbasis.h"
3 #include "bpol/normal-solvequadratic.h"
4 // demo-include "bpol/bitpol-normal.cc"
5 // demo-include "bpol/normal-mult.cc"
6 // demo-include "bpol/normal-primpoly.cc"
7 // demo-include "bpol/normal-irredpoly.cc"
8 #include "bmat/bitmat-funcs.h"
9
10 #include "bpol/bitpol-print.h"
11
12 #include "bits/parity.h"
13 #include "bits/bitrotate.h"
14 #include "bits/print-bin.h"
15
16 #include "nextarg.h" // NXARG()
17 #include "fxttypes.h" // ulong
18 #include "fxtio.h"
19 #include "fxtalloca.h"
20 #include "jjassert.h"
21
22 #include <cstdlib> // strtoul()
23
24
25 //% Multiplication with a normal basis for GF(2**n).
26
27 int
main(int argc,char ** argv)28 main(int argc, char **argv)
29 {
30 ulong n = 5;
31 NXARG(n, "The n in GF(2**n)");
32
33 ulong c = highbit_normal_primpoly[n]; // 'x' is always a generator
34 RESTARGS("Optionally supply nonzero coefficients of normal poly c");
35 if ( argc>2 ) c = (1UL<<n);
36 for (ulong k=2; k<(ulong)argc; ++k) c |= (1UL << strtoul(argv[k], nullptr, 10));
37
38 cout << endl;
39 print_bin("Normal poly: c=", c, n+1);
40 bitpol_print(" == ", c);
41 cout << endl;
42
43 ALLOCA(ulong, M, n); // multiplication matrix
44 const bool q = bitpol_normal_q(c, n, 0, M);
45 jjassert( q );
46 jjassert( q==bitpol_normal2_q(c, n) );
47 // bitmat_print("Multiplication matrix: M=", M, n);
48 // cout << endl;
49
50 const ulong pn = n;
51 const ulong nn = (1UL << n) - 1;
52
53 ulong g = 1UL; // 'x'
54 // ulong g = 7UL; // '1+x+x^2' // for type-1 bases and n=4, n=10
55 print_bin(" g=", g, pn);
56 cout << endl;
57 cout << endl;
58
59 cout << " k = :";
60 cout << " f=g**k";
61 cout << " Tr(f)";
62 cout << " x^2+x==f";
63 cout << endl;
64 const ulong one = (1UL<<n)-1; // one in normal basis representation
65 ulong f = one;
66
67 ulong k = 0;
68 do
69 {
70 cout << setw(4) << k;
71 print_bin(" = ", k, pn); cout << " : ";
72 print_bin(" ", f, pn);
73
74
75 ulong x; // solution to reduced quadratic equation
76 ulong t = normal_solve_reduced_quadratic_q(f, x); // trace is returned
77 cout << " " << ".1"[t];
78
79 if ( 0==t ) // solve x^2+x==f
80 {
81 // ulong x = normal_solve_reduced_quadratic(f);
82 print_bin(" x=", x, n);
83 }
84
85 f = normal_mult(f, g, M, n); // f *= g
86
87 ++k;
88 cout << endl;
89 }
90 while ( f!=one );
91
92 --k;
93 cout << " k = " << k << endl;
94 cout << " (2**n-1)/k = " << nn/k << endl;
95
96 return 0;
97 }
98 // -------------------------
99
100 /// Emacs:
101 /// Local Variables:
102 /// MyRelDir: "demo/gf2n"
103 /// makefile-dir: "../../"
104 /// make-target: "1demo DSRC=demo/gf2n/normalbasis-demo.cc"
105 /// make-target2: "1demo DSRC=demo/gf2n/normalbasis-demo.cc DEMOFLAGS=-DTIMING"
106 /// End:
107
108