Changeset b79b58 in git
 Timestamp:
 Apr 12, 2013, 3:43:28 PM (11 years ago)
 Branches:
 (u'fiekerDuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'c7af8613769b29c741d6c338945669719f1fc4f8')
 Children:
 efd410fc3eac114fbca114eb66d8070b61317f92
 Parents:
 102a88e6f12a4917862dddbee21516334b500c51
 gitauthor:
 Martin Lee <martinlee84@web.de>20130412 15:43:28+02:00
 gitcommitter:
 Martin Lee <martinlee84@web.de>20130502 11:42:36+02:00
 Location:
 factory
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

factory/cfNewtonPolygon.cc
r102a88e rb79b58 18 18 #include "cf_iter.h" 19 19 #include "cf_algorithm.h" 20 #include "cf_primes.h" 21 #include "cf_reval.h" 20 22 #include "cfNewtonPolygon.h" 21 23 #include "templates/ftmpl_functions.h" … … 937 939 On (SW_RATIONAL); 938 940 941 for (int i= 0; i < sizeOfNewtonPolygon; i++) 942 delete [] newtonPolyg[i]; 943 944 delete [] newtonPolyg; 945 939 946 return result; 940 947 } 941 948 949 bool 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 1025 bool 1026 modularIrredTestWithShift (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 84 84 ); 85 85 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 91 bool 92 modularIrredTest (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 101 bool 102 modularIrredTestWithShift (const CanonicalForm& F ///< [in] a bivariate polynomial 103 ///< irreducible over Z 104 ); 105 88 106 89 107 #ifdef HAVE_NTL
Note: See TracChangeset
for help on using the changeset viewer.