gf2xfactoring.c

数值算法库for Unix

   if (r == 0) {
      factors.SetLength(0);
      return;
   }

   if (r == 1) {
      factors.SetLength(1);
      factors[0] = f;
      return;
   }

   if (d == 1) {
      // factors are X and X+1

      factors.SetLength(2);
      SetX(factors[0]);
      SetX(factors[1]);
      SetCoeff(factors[1], 0);
      return;
   }

   
   double t;
   if (verbose) { 
      cerr << "computing EDF(" << d << "," << r << ")..."; 
      t = GetTime(); 
   }

   factors.SetLength(0);

   RecEDF(factors, f, d);

   if (verbose) cerr << (GetTime()-t) << "\n";
}


void SFCanZass(vec_GF2X& factors, const GF2X& ff, long verbose)
{
   GF2X f = ff;

   if (IsZero(f)) Error("SFCanZass: bad args");

   if (deg(f) == 0) {
      factors.SetLength(0);
      return;
   }

   if (deg(f) == 1) {
      factors.SetLength(1);
      factors[0] = f;
      return;
   }

   factors.SetLength(0);

   double t;

   
   vec_pair_GF2X_long u;
   if (verbose) { cerr << "computing DDF..."; t = GetTime(); }
   DDF(u, f, verbose);
   if (verbose) { 
      t = GetTime()-t; 
      cerr << "DDF time: " << t << "\n";
   }

   vec_GF2X v;

   long i;
   for (i = 0; i < u.length(); i++) {
      const GF2X& g = u[i].a;
      long d = u[i].b;
      long r = deg(g)/d;

      if (r == 1) {
         // g is already irreducible

         append(factors, g);
      }
      else {
         // must perform EDF

         EDF(v, g, d, verbose);
         append(factors, v);
      }
   }
}
   
void CanZass(vec_pair_GF2X_long& factors, const GF2X& f, long verbose)
{
   if (IsZero(f))
      Error("CanZass: bad args");

   double t;
   vec_pair_GF2X_long sfd;
   vec_GF2X x;

   
   if (verbose) { cerr << "square-free decomposition..."; t = GetTime(); }
   SquareFreeDecomp(sfd, f);
   if (verbose) cerr << (GetTime()-t) << "\n";

   factors.SetLength(0);

   long i, j;

   for (i = 0; i < sfd.length(); i++) {
      if (verbose) {
         cerr << "factoring multiplicity " << sfd[i].b 
              << ", deg = " << deg(sfd[i].a) << "\n";
      }

      SFCanZass(x, sfd[i].a, verbose);

      for (j = 0; j < x.length(); j++)
         append(factors, cons(x[j], sfd[i].b));
   }
}

void mul(GF2X& f, const vec_pair_GF2X_long& v)
{
   long i, j, n;

   n = 0;
   for (i = 0; i < v.length(); i++)
      n += v[i].b*deg(v[i].a);

   GF2X g;

   set(g);
   for (i = 0; i < v.length(); i++)
      for (j = 0; j < v[i].b; j++) {
         mul(g, g, v[i].a);
      }

   f = g;
}



static
void ConvertBits(GF2X& x, _ntl_ulong b)
{
   clear(x);
   long i;

   for (i = NTL_BITS_PER_LONG-1; i >= 0; i--)
      if (b & (1UL << i))
         SetCoeff(x, i);

}

void BuildIrred(GF2X& f, long n)
{
   if (n <= 0)
      Error("BuildIrred: n must be positive");

   if (n >= (1L << (NTL_BITS_PER_LONG-4))) Error("overflow in BuildIrred");

   if (n == 1) {
      SetX(f);
      return;
   }

   GF2X g;

   _ntl_ulong i;

   i = 0;
   do {
      ConvertBits(g, 2*i+1);
      SetCoeff(g, n);
      i++;
   } while (!IterIrredTest(g));

   f = g;

}

void BuildRandomIrred(GF2X& f, const GF2X& g)
{
   GF2XModulus G;
   GF2X h, ff;

   build(G, g);
   do {
      random(h, deg(g));
      IrredPolyMod(ff, h, G);
   } while (deg(ff) < deg(g));

   f = ff;
}




short GF2X_irred_tab[][3] = 

{{0,0,0}, {0,0,0},
{1,0,0}, {1,0,0}, {1,0,0}, {2,0,0}, {1,0,0}, {1,0,0}, 
{4,3,1}, {1,0,0}, {3,0,0}, {2,0,0}, {3,0,0}, {4,3,1}, 
{5,0,0}, {1,0,0}, {5,3,1}, {3,0,0}, {3,0,0}, {5,2,1}, 
{3,0,0}, {2,0,0}, {1,0,0}, {5,0,0}, {4,3,1}, {3,0,0}, 
{4,3,1}, {5,2,1}, {1,0,0}, {2,0,0}, {1,0,0}, {3,0,0}, 
{7,3,2}, {10,0,0}, {7,0,0}, {2,0,0}, {9,0,0}, {6,4,1}, 
{6,5,1}, {4,0,0}, {5,4,3}, {3,0,0}, {7,0,0}, {6,4,3}, 
{5,0,0}, {4,3,1}, {1,0,0}, {5,0,0}, {5,3,2}, {9,0,0}, 
{4,3,2}, {6,3,1}, {3,0,0}, {6,2,1}, {9,0,0}, {7,0,0}, 
{7,4,2}, {4,0,0}, {19,0,0}, {7,4,2}, {1,0,0}, {5,2,1}, 
{29,0,0}, {1,0,0}, {4,3,1}, {18,0,0}, {3,0,0}, {5,2,1}, 
{9,0,0}, {6,5,2}, {5,3,1}, {6,0,0}, {10,9,3}, {25,0,0}, 
{35,0,0}, {6,3,1}, {21,0,0}, {6,5,2}, {6,5,3}, {9,0,0}, 
{9,4,2}, {4,0,0}, {8,3,1}, {7,4,2}, {5,0,0}, {8,2,1}, 
{21,0,0}, {13,0,0}, {7,6,2}, {38,0,0}, {27,0,0}, {8,5,1}, 
{21,0,0}, {2,0,0}, {21,0,0}, {11,0,0}, {10,9,6}, {6,0,0}, 
{11,0,0}, {6,3,1}, {15,0,0}, {7,6,1}, {29,0,0}, {9,0,0}, 
{4,3,1}, {4,0,0}, {15,0,0}, {9,7,4}, {17,0,0}, {5,4,2}, 
{33,0,0}, {10,0,0}, {5,4,3}, {9,0,0}, {5,3,2}, {8,7,5}, 
{4,2,1}, {5,2,1}, {33,0,0}, {8,0,0}, {4,3,1}, {18,0,0}, 
{6,2,1}, {2,0,0}, {19,0,0}, {7,6,5}, {21,0,0}, {1,0,0}, 
{7,2,1}, {5,0,0}, {3,0,0}, {8,3,2}, {17,0,0}, {9,8,2}, 
{57,0,0}, {11,0,0}, {5,3,2}, {21,0,0}, {8,7,1}, {8,5,3}, 
{15,0,0}, {10,4,1}, {21,0,0}, {5,3,2}, {7,4,2}, {52,0,0}, 
{71,0,0}, {14,0,0}, {27,0,0}, {10,9,7}, {53,0,0}, {3,0,0}, 
{6,3,2}, {1,0,0}, {15,0,0}, {62,0,0}, {9,0,0}, {6,5,2}, 
{8,6,5}, {31,0,0}, {5,3,2}, {18,0,0}, {27,0,0}, {7,6,3}, 
{10,8,7}, {9,8,3}, {37,0,0}, {6,0,0}, {15,3,2}, {34,0,0}, 
{11,0,0}, {6,5,2}, {1,0,0}, {8,5,2}, {13,0,0}, {6,0,0}, 
{11,3,2}, {8,0,0}, {31,0,0}, {4,2,1}, {3,0,0}, {7,6,1}, 
{81,0,0}, {56,0,0}, {9,8,7}, {24,0,0}, {11,0,0}, {7,6,5}, 
{6,5,2}, {6,5,2}, {8,7,6}, {9,0,0}, {7,2,1}, {15,0,0}, 
{87,0,0}, {8,3,2}, {3,0,0}, {9,4,2}, {9,0,0}, {34,0,0}, 
{5,3,2}, {14,0,0}, {55,0,0}, {8,7,1}, {27,0,0}, {9,5,2}, 
{10,9,5}, {43,0,0}, {9,3,1}, {6,0,0}, {7,0,0}, {11,10,8}, 
{105,0,0}, {6,5,2}, {73,0,0}, {23,0,0}, {7,3,1}, {45,0,0}, 
{11,0,0}, {8,4,1}, {7,0,0}, {8,6,2}, {5,4,2}, {33,0,0}, 
{9,8,3}, {32,0,0}, {10,7,3}, {10,9,4}, {113,0,0}, {10,4,1}, 
{8,7,6}, {26,0,0}, {9,4,2}, {74,0,0}, {31,0,0}, {9,6,1}, 
{5,0,0}, {7,4,1}, {73,0,0}, {36,0,0}, {8,5,3}, {70,0,0}, 
{95,0,0}, {8,5,1}, {111,0,0}, {6,4,1}, {11,2,1}, {82,0,0}, 
{15,14,10}, {35,0,0}, {103,0,0}, {7,4,2}, {15,0,0}, {46,0,0}, 
{7,2,1}, {52,0,0}, {10,5,2}, {12,0,0}, {71,0,0}, {10,6,2}, 
{15,0,0}, {7,6,4}, {9,8,4}, {93,0,0}, {9,6,2}, {42,0,0}, 
{47,0,0}, {8,6,3}, {25,0,0}, {7,6,1}, {53,0,0}, {58,0,0}, 
{9,3,2}, {23,0,0}, {67,0,0}, {11,10,9}, {63,0,0}, {12,6,3}, 
{5,0,0}, {5,0,0}, {9,5,2}, {93,0,0}, {35,0,0}, {12,7,5}, 
{53,0,0}, {10,7,5}, {69,0,0}, {71,0,0}, {11,10,1}, {21,0,0}, 
{5,3,2}, {12,11,5}, {37,0,0}, {11,6,1}, {33,0,0}, {48,0,0}, 
{7,3,2}, {5,0,0}, {11,8,4}, {11,6,4}, {5,0,0}, {9,5,2}, 
{41,0,0}, {1,0,0}, {11,2,1}, {102,0,0}, {7,3,1}, {8,4,2}, 
{15,0,0}, {10,6,4}, {93,0,0}, {7,5,3}, {9,7,4}, {79,0,0}, 
{15,0,0}, {10,9,1}, {63,0,0}, {7,4,2}, {45,0,0}, {36,0,0}, 
{4,3,1}, {31,0,0}, {67,0,0}, {10,3,1}, {51,0,0}, {10,5,2}, 
{10,3,1}, {34,0,0}, {8,3,1}, {50,0,0}, {99,0,0}, {10,6,2}, 
{89,0,0}, {2,0,0}, {5,2,1}, {10,7,2}, {7,4,1}, {55,0,0}, 
{4,3,1}, {16,10,7}, {45,0,0}, {10,8,6}, {125,0,0}, {75,0,0}, 
{7,2,1}, {22,0,0}, {63,0,0}, {11,10,3}, {103,0,0}, {6,5,2}, 
{53,0,0}, {34,0,0}, {13,11,6}, {69,0,0}, {99,0,0}, {6,5,1}, 
{10,9,7}, {11,10,2}, {57,0,0}, {68,0,0}, {5,3,2}, {7,4,1}, 
{63,0,0}, {8,5,3}, {9,0,0}, {9,6,5}, {29,0,0}, {21,0,0}, 
{7,3,2}, {91,0,0}, {139,0,0}, {8,3,2}, {111,0,0}, {8,7,2}, 
{8,6,5}, {16,0,0}, {8,7,5}, {41,0,0}, {43,0,0}, {10,8,5}, 
{47,0,0}, {5,2,1}, {81,0,0}, {90,0,0}, {12,3,2}, {6,0,0}, 
{83,0,0}, {8,7,1}, {159,0,0}, {10,9,5}, {9,0,0}, {28,0,0}, 
{13,10,6}, {7,0,0}, {135,0,0}, {11,6,5}, {25,0,0}, {12,7,6}, 
{7,6,2}, {26,0,0}, {5,3,2}, {152,0,0}, {171,0,0}, {9,8,5}, 
{65,0,0}, {13,8,2}, {141,0,0}, {71,0,0}, {5,3,2}, {87,0,0}, 
{10,4,3}, {12,10,3}, {147,0,0}, {10,7,6}, {13,0,0}, {102,0,0}, 
{9,5,2}, {107,0,0}, {199,0,0}, {15,5,4}, {7,0,0}, {5,4,2}, 
{149,0,0}, {25,0,0}, {9,7,2}, {12,0,0}, {63,0,0}, {11,6,5}, 
{105,0,0}, {10,8,7}, {14,6,1}, {120,0,0}, {13,4,3}, {33,0,0}, 
{12,11,5}, {12,9,5}, {165,0,0}, {6,2,1}, {65,0,0}, {49,0,0}, 
{4,3,1}, {7,0,0}, {7,5,2}, {10,6,1}, {81,0,0}, {7,6,4}, 
{105,0,0}, {73,0,0}, {11,6,4}, {134,0,0}, {47,0,0}, {16,10,1}, 
{6,5,4}, {15,6,4}, {8,6,1}, {38,0,0}, {18,9,6}, {16,0,0}, 
{203,0,0}, {12,5,2}, {19,0,0}, {7,6,1}, {73,0,0}, {93,0,0}, 
{19,18,13}, {31,0,0}, {14,11,6}, {11,6,1}, {27,0,0}, {9,5,2}, 
{9,0,0}, {1,0,0}, {11,3,2}, {200,0,0}, {191,0,0}, {9,8,4}, 
{9,0,0}, {16,15,7}, {121,0,0}, {104,0,0}, {15,9,6}, {138,0,0}, 
{9,6,5}, {9,6,4}, {105,0,0}, {17,16,6}, {81,0,0}, {94,0,0}, 
{4,3,1}, {83,0,0}, {219,0,0}, {11,6,3}, {7,0,0}, {10,5,3}, 
{17,0,0}, {76,0,0}, {16,5,2}, {78,0,0}, {155,0,0}, {11,6,5}, 
{27,0,0}, {5,4,2}, {8,5,4}, {3,0,0}, {15,14,6}, {156,0,0}, 
{23,0,0}, {13,6,3}, {9,0,0}, {8,7,3}, {69,0,0}, {10,0,0}, 
{8,5,2}, {26,0,0}, {67,0,0}, {14,7,4}, {21,0,0}, {12,10,2}, 
{33,0,0}, {79,0,0}, {15,11,2}, {32,0,0}, {39,0,0}, {13,6,2}, 
{167,0,0}, {6,4,1}, {97,0,0}, {47,0,0}, {11,6,2}, {42,0,0}, 
{10,7,3}, {10,5,4}, {1,0,0}, {4,3,2}, {161,0,0}, {8,6,2}, 
{7,5,3}, {94,0,0}, {195,0,0}, {10,5,4}, {9,0,0}, {13,10,4}, 
{8,6,1}, {16,0,0}, {8,3,1}, {122,0,0}, {8,2,1}, {13,7,4}, 
{10,5,3}, {16,4,3}, {193,0,0}, {135,0,0}, {19,16,9}, {39,0,0}, 
{10,8,7}, {10,9,4}, {153,0,0}, {7,6,5}, {73,0,0}, {34,0,0}, 
{11,9,6}, {71,0,0}, {11,4,2}, {14,7,3}, {163,0,0}, {11,6,1}, 
{153,0,0}, {28,0,0}, {15,7,6}, {77,0,0}, {67,0,0}, {10,5,2}, 
{12,8,1}, {10,6,4}, {13,0,0}, {146,0,0}, {13,4,3}, {25,0,0}, 
{23,22,16}, {12,9,7}, {237,0,0}, {13,7,6}, {85,0,0}, {130,0,0}, 
{14,13,3}, {88,0,0}, {7,5,2}, {11,6,1}, {35,0,0}, {10,4,3}, 
{93,0,0}, {9,6,4}, {13,6,3}, {86,0,0}, {19,0,0}, {9,2,1}, 
{273,0,0}, {14,12,9}, {7,6,1}, {30,0,0}, {9,5,2}, {201,0,0}, 
{215,0,0}, {6,4,3}, {105,0,0}, {10,7,5}, {165,0,0}, {105,0,0}, 
{19,13,6}, {31,0,0}, {127,0,0}, {10,4,2}, {81,0,0}, {19,10,4}, 
{45,0,0}, {211,0,0}, {19,10,3}, {200,0,0}, {295,0,0}, {9,8,5}, 
{9,0,0}, {12,6,5}, {297,0,0}, {68,0,0}, {11,6,5}, {133,0,0}, 
{251,0,0}, {13,8,4}, {223,0,0}, {6,5,2}, {7,4,2}, {307,0,0}, 
{9,2,1}, {101,0,0}, {39,0,0}, {14,10,4}, {217,0,0}, {14,9,1}, 
{6,5,1}, {16,0,0}, {14,3,2}, {11,0,0}, {119,0,0}, {11,3,2}, 
{11,6,5}, {11,8,4}, {249,0,0}, {5,0,0}, {13,3,1}, {37,0,0}, 
{3,0,0}, {14,0,0}, {93,0,0}, {10,8,7}, {33,0,0}, {88,0,0}, 
{7,5,4}, {38,0,0}, {55,0,0}, {15,4,2}, {11,0,0}, {12,11,4}, 
{21,0,0}, {107,0,0}, {11,9,8}, {33,0,0}, {10,7,2}, {18,7,3}, 
{147,0,0}, {5,4,2}, {153,0,0}, {15,0,0}, {11,6,5}, {28,0,0}, 
{11,7,4}, {6,3,1}, {31,0,0}, {8,4,3}, {15,5,3}, {66,0,0}, 
{23,16,9}, {11,9,3}, {171,0,0}, {11,6,1}, {209,0,0}, {4,3,1}, 
{197,0,0}, {13,0,0}, {19,14,6}, {14,0,0}, {79,0,0}, {13,6,2}, 
{299,0,0}, {15,8,2}, {169,0,0}, {177,0,0}, {23,10,2}, {267,0,0}, 
{215,0,0}, {15,10,1}, {75,0,0}, {16,4,2}, {37,0,0}, {12,7,1}, 
{8,3,2}, {17,0,0}, {12,11,8}, {15,8,5}, {15,0,0}, {4,3,1}, 
{13,12,4}, {92,0,0}, {5,4,3}, {41,0,0}, {23,0,0}, {7,4,1}, 
{183,0,0}, {16,7,1}, {165,0,0}, {150,0,0}, {9,6,4}, {9,0,0}, 
{231,0,0}, {16,10,4}, {207,0,0}, {9,6,5}, {5,0,0}, {180,0,0}, 
{4,3,2}, {58,0,0}, {147,0,0}, {8,6,2}, {343,0,0}, {8,7,2}, 
{11,6,1}, {44,0,0}, {13,8,6}, {5,0,0}, {347,0,0}, {18,16,8},