1 | |
---|
2 | /**************************************************************************\ |
---|
3 | |
---|
4 | MODULE: GF2XFactoring |
---|
5 | |
---|
6 | SUMMARY: |
---|
7 | |
---|
8 | Routines are provided for factorization in F_2[X], as well as routines |
---|
9 | for related problems such as testing irreducibility and constructing |
---|
10 | irreducible polynomials of given degree. |
---|
11 | |
---|
12 | \**************************************************************************/ |
---|
13 | |
---|
14 | #include <NTL/GF2X.h> |
---|
15 | #include <NTL/pair_GF2X_long.h> |
---|
16 | |
---|
17 | void SquareFreeDecomp(vec_pair_GF2X_long& u, const GF2X& f); |
---|
18 | vec_pair_GF2X_long SquareFreeDecomp(const GF2X& f); |
---|
19 | |
---|
20 | // Performs square-free decomposition. f must be monic. If f = |
---|
21 | // prod_i g_i^i, then u is set to a list of pairs (g_i, i). The list |
---|
22 | // is is increasing order of i, with trivial terms (i.e., g_i = 1) |
---|
23 | // deleted. |
---|
24 | |
---|
25 | |
---|
26 | void DDF(vec_pair_GF2X_long& factors, const GF2X& f, long verbose=0); |
---|
27 | vec_pair_GF2X_long DDF(const GF2X& f, long verbose=0); |
---|
28 | |
---|
29 | // This computes a distinct-degree factorization. The input must be |
---|
30 | // monic and square-free. factors is set to a list of pairs (g, d), |
---|
31 | // where g is the product of all irreducible factors of f of degree d. |
---|
32 | // Only nontrivial pairs (i.e., g != 1) are included. |
---|
33 | |
---|
34 | |
---|
35 | |
---|
36 | void EDF(vec_GF2X& factors, const GF2X& f, long d, long verbose=0); |
---|
37 | vec_GF2X EDF(const GF2X& f, long d, long verbose=0); |
---|
38 | |
---|
39 | // Performs equal-degree factorization. f is monic, square-free, and |
---|
40 | // all irreducible factors have same degree. d = degree of |
---|
41 | // irreducible factors of f |
---|
42 | |
---|
43 | void SFCanZass(vec_GF2X& factors, const GF2X& f, long verbose=0); |
---|
44 | vec_GF2X SFCanZass(const GF2X& f, long verbose=0); |
---|
45 | |
---|
46 | |
---|
47 | // Assumes f is monic and square-free. returns list of factors of f. |
---|
48 | |
---|
49 | |
---|
50 | void CanZass(vec_pair_GF2X_long& factors, const GF2X& f, long verbose=0); |
---|
51 | vec_pair_GF2X_long CanZass(const GF2X& f, long verbose=0); |
---|
52 | |
---|
53 | // returns a list of factors, with multiplicities. f must be monic. |
---|
54 | // Calls SquareFreeDecomp and SFCanZass. |
---|
55 | |
---|
56 | |
---|
57 | void mul(GF2X& f, const vec_pair_GF2X_long& v); |
---|
58 | GF2X mul(const vec_pair_GF2X_long& v); |
---|
59 | |
---|
60 | // multiplies polynomials, with multiplicities |
---|
61 | |
---|
62 | |
---|
63 | /**************************************************************************\ |
---|
64 | |
---|
65 | Irreducible Polynomials |
---|
66 | |
---|
67 | \**************************************************************************/ |
---|
68 | |
---|
69 | long IterIrredTest(const GF2X& f); |
---|
70 | |
---|
71 | // performs an iterative deterministic irreducibility test, based on |
---|
72 | // DDF. Fast on average (when f has a small factor). |
---|
73 | |
---|
74 | void BuildSparseIrred(GF2X& f, long n); |
---|
75 | GF2X BuildSparseIrred_GF2X(long n); |
---|
76 | |
---|
77 | // Builds a monic irreducible polynomial of degree n. |
---|
78 | // If there is an irreducible trinomial X^n + X^k + 1, |
---|
79 | // then the one with minimal k is chosen. |
---|
80 | // Otherwise, if there is an irreducible pentanomial |
---|
81 | // X^n + X^k3 + X^k2 + x^k1 + 1, then the one with minimal |
---|
82 | // k3 is chosen (minimizing first k2 and then k1). |
---|
83 | // Otherwise, if there is niether an irreducible trinomial |
---|
84 | // or pentanomial, the routine result from BuildIrred (see below) |
---|
85 | // is chosen---this is probably only of academic interest, |
---|
86 | // since it a reasonable, but unproved, conjecture that they |
---|
87 | // exist for every n > 1. |
---|
88 | |
---|
89 | // For n <= 2048, the polynomial is constructed |
---|
90 | // by table lookup in a pre-computed table. |
---|
91 | |
---|
92 | // The GF2XModulus data structure and routines (and indirectly GF2E) |
---|
93 | // are optimized to deal with the output from BuildSparseIrred. |
---|
94 | |
---|
95 | void BuildIrred(GF2X& f, long n); |
---|
96 | GF2X BuildIrred_GF2X(long n); |
---|
97 | |
---|
98 | // Build a monic irreducible poly of degree n. The polynomial |
---|
99 | // constructed is "canonical" in the sense that it is of the form |
---|
100 | // f=X^n + g, where the bits of g are the those of the smallest |
---|
101 | // non-negative integer that make f irreducible. |
---|
102 | |
---|
103 | // The GF2XModulus data structure and routines (and indirectly GF2E) |
---|
104 | // are optimized to deal with the output from BuildIrred. |
---|
105 | |
---|
106 | // Note that the output from BuildSparseIrred will generally yield |
---|
107 | // a "better" representation (in terms of efficiency) for |
---|
108 | // GF(2^n) than the output from BuildIrred. |
---|
109 | |
---|
110 | |
---|
111 | |
---|
112 | void BuildRandomIrred(GF2X& f, const GF2X& g); |
---|
113 | GF2X BuildRandomIrred(const GF2X& g); |
---|
114 | |
---|
115 | // g is a monic irreducible polynomial. Constructs a random monic |
---|
116 | // irreducible polynomial f of the same degree. |
---|
117 | |
---|