Changeset b79b58 in git


Ignore:
Timestamp:
Apr 12, 2013, 3:43:28 PM (9 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '48f1dd268d0ff74ef2f7dccbf02545425002ddcc')
Children:
efd410fc3eac114fbca114eb66d8070b61317f92
Parents:
102a88e6f12a4917862dddbee21516334b500c51
git-author:
Martin Lee <martinlee84@web.de>2013-04-12 15:43:28+02:00
git-committer:
Martin Lee <martinlee84@web.de>2013-05-02 11:42:36+02:00
Message:
chg: added naive implementations of abs. irred. tests from
     Bertone, Cheze, Galligo
Location:
factory
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • factory/cfNewtonPolygon.cc

    r102a88e rb79b58  
    1818#include "cf_iter.h"
    1919#include "cf_algorithm.h"
     20#include "cf_primes.h"
     21#include "cf_reval.h"
    2022#include "cfNewtonPolygon.h"
    2123#include "templates/ftmpl_functions.h"
     
    937939    On (SW_RATIONAL);
    938940
     941  for (int i= 0; i < sizeOfNewtonPolygon; i++)
     942    delete [] newtonPolyg[i];
     943
     944  delete [] newtonPolyg;
     945
    939946  return result;
    940947}
    941948
     949bool modularIrredTest (const CanonicalForm& F)
     950{
     951  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
     952  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
     953
     954  bool isRat= isOn (SW_RATIONAL);
     955  if (isRat)
     956    Off (SW_RATIONAL);
     957
     958  if (isRat)
     959    ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
     960
     961  CanonicalForm Fp, N= maxNorm (F);
     962  int tdeg= totaldegree (F);
     963
     964  int i= 0;
     965  //TODO: maybe it's better to choose the characteristic as large as possible
     966  //      as factorization over large finite field will be faster
     967  //TODO: handle those cases where our factory primes are not enough
     968  //TODO: factorize coefficients corresponding to the vertices of the Newton
     969  //      polygon and only try the obtained factors
     970  if (N < cf_getSmallPrime (cf_getNumSmallPrimes()-1))
     971  {
     972    while (i < cf_getNumSmallPrimes() && N > cf_getSmallPrime(i))
     973    {
     974      setCharacteristic (cf_getSmallPrime (i));
     975      Fp= F.mapinto();
     976      i++;
     977      if (totaldegree (Fp) == tdeg)
     978      {
     979        if (absIrredTest (Fp))
     980        {
     981          CFFList factors= factorize (Fp);
     982          if (factors.length() == 2 && factors.getLast().exp() == 1)
     983          {
     984            if (isRat)
     985              On (SW_RATIONAL);
     986            setCharacteristic (0);
     987            return true;
     988          }
     989        }
     990      }
     991      setCharacteristic (0);
     992    }
     993  }
     994  else
     995  {
     996    while (i < cf_getNumPrimes() && N > cf_getPrime (i))
     997    {
     998      setCharacteristic (cf_getPrime (i));
     999      Fp= F.mapinto();
     1000      i++;
     1001      if (totaldegree (Fp) == tdeg)
     1002      {
     1003        if (absIrredTest (Fp))
     1004        {
     1005          CFFList factors= factorize (Fp);
     1006          if (factors.length() == 2 && factors.getLast().exp() == 1)
     1007          {
     1008            if (isRat)
     1009              On (SW_RATIONAL);
     1010            setCharacteristic (0);
     1011            return true;
     1012          }
     1013        }
     1014      }
     1015      setCharacteristic (0);
     1016    }
     1017  }
     1018
     1019  if (isRat)
     1020    On (SW_RATIONAL);
     1021
     1022  return false;
     1023}
     1024
     1025bool
     1026modularIrredTestWithShift (const CanonicalForm& F)
     1027{
     1028  ASSERT (getNumVars (F) == 2, "expected bivariate polynomial");
     1029  ASSERT (factorize (F).length() <= 2, " expected irreducible polynomial");
     1030
     1031  bool isRat= isOn (SW_RATIONAL);
     1032  if (isRat)
     1033    Off (SW_RATIONAL);
     1034
     1035  if (isRat)
     1036    ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
     1037
     1038  Variable x= Variable (1);
     1039  Variable y= Variable (2);
     1040  CanonicalForm Fp;
     1041  int tdeg= totaldegree (F);
     1042
     1043  REvaluation E;
     1044
     1045  setCharacteristic (2);
     1046  Fp= F.mapinto();
     1047
     1048  E= REvaluation (1,2, FFRandom());
     1049
     1050  E.nextpoint();
     1051
     1052  Fp= Fp (x+E[1], x);
     1053  Fp= Fp (y+E[2], y);
     1054
     1055  if (tdeg == totaldegree (Fp))
     1056  {
     1057    if (absIrredTest (Fp))
     1058    {
     1059      CFFList factors= factorize (Fp);
     1060      if (factors.length() == 2 && factors.getLast().exp() == 1)
     1061      {
     1062        if (isRat)
     1063          On (SW_RATIONAL);
     1064        setCharacteristic (0);
     1065        return true;
     1066      }
     1067    }
     1068  }
     1069
     1070  E.nextpoint();
     1071
     1072  Fp= Fp (x+E[1], x);
     1073  Fp= Fp (y+E[2], y);
     1074
     1075  if (tdeg == totaldegree (Fp))
     1076  {
     1077    if (absIrredTest (Fp))
     1078    {
     1079      CFFList factors= factorize (Fp);
     1080      if (factors.length() == 2 && factors.getLast().exp() == 1)
     1081      {
     1082        if (isRat)
     1083          On (SW_RATIONAL);
     1084        setCharacteristic (0);
     1085        return true;
     1086      }
     1087    }
     1088  }
     1089
     1090  int i= 0;
     1091  while (cf_getSmallPrime (i) < 102)
     1092  {
     1093    setCharacteristic (cf_getSmallPrime (i));
     1094    i++;
     1095    E= REvaluation (1, 2, FFRandom());
     1096
     1097    for (int j= 0; j < 3; j++)
     1098    {
     1099      Fp= F.mapinto();
     1100      E.nextpoint();
     1101      Fp= Fp (x+E[1], x);
     1102      Fp= Fp (y+E[2], y);
     1103
     1104      if (tdeg == totaldegree (Fp))
     1105      {
     1106        if (absIrredTest (Fp))
     1107        {
     1108          CFFList factors= factorize (Fp);
     1109          if (factors.length() == 2 && factors.getLast().exp() == 1)
     1110          {
     1111            if (isRat)
     1112              On (SW_RATIONAL);
     1113            setCharacteristic (0);
     1114            return true;
     1115          }
     1116        }
     1117      }
     1118    }
     1119  }
     1120
     1121  setCharacteristic (0);
     1122  if (isRat)
     1123    On (SW_RATIONAL);
     1124
     1125  return false;
     1126}
     1127
     1128
  • factory/cfNewtonPolygon.h

    r102a88e rb79b58  
    8484             );
    8585
    86 //TODO add modular test from "Modular Las Vegas Algorithms
    87 // for Polynomial Absolute Factorization" by C. Bertone, G. Cheze, A. Galligo
     86/// modular absolute irreducibility test as described in "Modular Las Vegas
     87/// Algorithms for Polynomial Absolute Factorization" by C. Bertone, G. Cheze,
     88/// A. Galligo
     89///
     90/// @return true if F is absolutely irreducible, false otherwise
     91bool
     92modularIrredTest (const CanonicalForm& F ///< [in] a bivariate polynomial
     93                                         ///< irreducible over Z
     94                 );
     95
     96/// modular absolute irreducibility test with shift as described in "Modular Las
     97/// Vegas Algorithms for Polynomial Absolute Factorization" by C. Bertone,
     98/// G. Cheze, A. Galligo
     99///
     100/// @return true if F is absolutely irreducible, false otherwise
     101bool
     102modularIrredTestWithShift (const CanonicalForm& F ///< [in] a bivariate polynomial
     103                                                  ///< irreducible over Z
     104                          );
     105
    88106
    89107#ifdef HAVE_NTL
Note: See TracChangeset for help on using the changeset viewer.