1 // This file is part of the FXT library.
2 // Copyright (C) 2010, 2011 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 "fxttypes.h"
7 #include "bpol/bitpolmod-arith.h"
8 #include "mod/factor.h"
9
10
11 ulong
gf2n_order(ulong g,ulong c,ulong h,const factorization & mfact)12 gf2n_order(ulong g, ulong c, ulong h, const factorization &mfact)
13 // Return order of g \in GF(2**n) with field polynomial c.
14 // c must be irreducible
15 // h must be equal 1<<(deg(c)-1)
16 // mfact must contain the factorization of 2**deg(c)-1
17 // The routine may loop if either:
18 // - the polynomial c is reducible
19 // - deg(g) >= deg(c)
20 // - h is not set correctly
21 // - mfact is not set correctly
22 {
23 if ( 0==g ) return 0; // not in multiplicative group
24
25 ulong m = mfact.product();
26 ulong e = m;
27 for (ulong i=0; i<mfact.nprimes(); ++i)
28 {
29 ulong p = mfact.prime(i);
30 ulong f = mfact.primepow(i);
31
32 e /= f;
33
34 ulong g1 = bitpolmod_power(g, e, c, h);
35 while ( g1!=1 )
36 {
37 g1 = bitpolmod_power(g1, p, c, h);
38 e *= p;
39 }
40 }
41
42 return e;
43 }
44 // -------------------------
45