1 // This file is part of the FXT library.
2 // Copyright (C) 2010, 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 "bpol/gf2n-trace.h"
7 #include "bpol/bitpolmod-arith.h"
8 #include "bpol/bitpolmod-minpoly.h"
9
10 #include "fxttypes.h"
11
12 //#include "jjassert.h"
13
14
15 ulong
gf2n_xx2k_trace(ulong c,ulong deg)16 gf2n_xx2k_trace(ulong c, ulong deg)
17 // Return vector T of traces T[k]=trace(ek),
18 // where ek = x*x^(2^k), k=0..deg-1, and
19 // x is a root of the irreducible polynomial C.
20 // Must have: deg == degree(C)
21 //
22 // The polynomial C is normal if and only if
23 // gcd(x^deg-1, T)==1 where T is taken as a polynomial.
24 // The dual basis is generated by sum(k=0..deg-1, D[k]*x^(2^k)) where
25 // D = T^-1 mod x^deg-1. The dual basis is also normal.
26 // If the only nonzero component of T is T[0], then
27 // the basis is self-dual.
28 {
29 if ( c==3 ) return 1UL; // x+1 is self-dual
30
31 const ulong tv = gf2n_trace_vector_x(c, deg); // traces of x^k
32 ulong rt = 2UL; // root of C
33 const ulong h = 1UL << (deg-1); // aux
34
35 ulong T = 0;
36 for (ulong k=0; k<deg; ++k)
37 {
38 ulong ek = bitpolmod_times_x(rt, c, h); // == x*x^(2^k)
39 ulong tk = gf2n_fast_trace(ek, tv); // == sum(ek[i]*tk[i])
40 T |= (tk<<k);
41 rt = bitpolmod_square(rt, c, h);
42 }
43
44 return T;
45 }
46 // -------------------------
47
48
49 ulong
gf2n_dual_normal(ulong c,ulong deg,ulong ntc,ulong * ntd)50 gf2n_dual_normal(ulong c, ulong deg, ulong ntc/*=0*/, ulong *ntd/*=0*/)
51 // Return the minimal polynomial CS for the dual (normal) basis
52 // with the irreducible normal polynomial C.
53 // Return zero if C is not normal.
54 // Must have: deg == degree(C).
55 // If ntc is supplied it must be equal to gf2n_xx2k_trace(c, deg).
56 // If ntd is nonzero, ntc^-1 (mod x^deg-1) is written to it.
57 {
58 if ( 0==ntc ) ntc = gf2n_xx2k_trace(c, deg);
59 const ulong d = bitpolmod_inverse(ntc, 1 | (1UL<<deg) ); // ntc=d^-1 (mod x^deg-1)
60 if ( 0==d ) return 0; // C not normal
61 if ( nullptr != ntd ) *ntd = d;
62
63 const ulong h = 1UL << (deg-1); // aux
64 ulong alpha = 2UL; // 'x', a root of C
65 ulong beta = 0; // root of the dual polynomial
66 for (ulong m=d; m!=0; m>>=1)
67 {
68 if ( m & 1 ) beta ^= alpha;
69 alpha = bitpolmod_square(alpha, c, h);
70 }
71
72 ulong cs; // minimal polynomial of beta
73 bitpolmod_minpoly(beta, c, deg, cs);
74 // csdeg = bitpol_minpoly(beta, c, deg, cs);
75 // jjassert( deg == csdeg );
76
77 return cs;
78 }
79 // -------------------------
80