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