1 // This file is part of the FXT library.
2 // Copyright (C) 2010, 2011, 2012, 2018 Joerg Arndt
3 // License: GNU General Public License version 3 or later,
4 // see the file COPYING.txt in the main directory.
5
6 #include "bmat/bitmat-funcs.h"
7 #include "bmat/bitmat-inline.h" // bitmat_get()
8 #include "bpol/bitpolmod-arith.h"
9 #include "bpol/bitpol-irred.h"
10
11 #include "bpol/normalpoly-dual.h" // gf2n_xx2k_trace()
12
13 #include "fxtalloca.h"
14
15 #include "fxttypes.h" // ulong
16
17 //#include "fxtio.h"
18
19 bool
bitpol_normal2_q(ulong c,ulong n)20 bitpol_normal2_q(ulong c, ulong n)
21 // Return whether polynomial c (of degree n) is normal.
22 // Must have: c irreducible.
23 {
24 const ulong t = gf2n_xx2k_trace(c, n);
25 const ulong xn1 = (1UL<<n) | 1UL; // x^n-1
26 return ( 1 == bitpol_gcd(t, xn1) );
27 }
28 // -------------------------
29
30
31 bool
bitpol_normal_q(ulong c,ulong n,ulong iq,ulong * M)32 bitpol_normal_q(ulong c, ulong n, ulong iq/*=nullptr*/, ulong *M/*=nullptr*/)
33 // Return whether polynomial c (of degree n) is normal.
34 // Set iq to 1 for polynomials known to be irreducible.
35 // If M is given then the multiplication matrix is computed.
36 {
37 const ulong h = 1UL << (n-1);
38 if ( 0==(c & h) ) return false; // polynomial trace must be one
39
40 if ( 0==iq )
41 {
42 iq = bitpol_irreducible_q(c, h);
43 if ( 0==iq ) return false; // polynomial reducible ==> not normal
44 }
45
46 if ( c==3 ) // special case with c=x+1
47 {
48 if ( M ) M[0] = 1;
49 return true;
50 }
51
52 ALLOCA(ulong, A, n);
53 ulong v = 2UL; // 'x'
54 for (ulong k=0; k<n; ++k)
55 {
56 A[k] = v;
57 v = bitpolmod_square(v, c, h);
58 }
59
60 ALLOCA(ulong, Ai, n);
61 bool q = bitmat_inverse(A, n, Ai); // try to invert
62 if ( 0==q ) return false; // polynomial is not normal
63
64 if ( nullptr != M ) // compute multiplication matrix
65 {
66 // make valgrind happy (we have partial writes to words of M[]):
67 for (ulong k=0; k<n; ++k) M[k] = 0;
68
69 ALLOCA(ulong, C, n);
70 bitmat_companion(c, n, C);
71 bitmat_transpose(C, n, C);
72
73 // bitmat_print("A=", A, n);
74 // bitmat_print("A^-1=", Ai, n);
75 // bitmat_print("C^T=", C, n);
76
77 bitmat_mult_MM(A, C, n, A); // A*C^T
78 bitmat_mult_MM(A, Ai, n, A); // D=A*C^T*A^{-1}
79
80 // bitmat_print("D=A*C^T*A^{-1}=", A, n);
81
82 ulong im = 0; // == -i mod n
83 for (ulong i=0; i<n; ++i)
84 {
85 // cout << " i=" << i << " im=" << im << endl;
86 ulong jm = im; // == j-i mod n
87 for (ulong j=0; j<n; ++j)
88 {
89 bitmat_set(M, i, j, bitmat_get(A, jm, im));
90 ++jm; if ( n==jm ) { jm = 0; } // ++jm (mod n)
91 }
92 if ( 0==im ) { im=n-1; } else { --im; } // --im (mod n)
93 }
94
95 // bitmat_print("M=", M, n);
96 }
97
98 return 1;
99 }
100 // -------------------------
101