[2cfffe] | 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 | |
---|