1 // -*- c++ -*-
2 //*****************************************************************************
3 /** @file cf_cyclo.cc
4 *
5 * Compute cyclotomic polynomials and factorize integers by brute force
6 *
7 * @par Copyright:
8 * (c) by The SINGULAR Team, see LICENSE file
9 *
10 * @author Martin Lee
11 * @date 29.01.2010
12 **/
13 //*****************************************************************************
14
15
16 #include "config.h"
17
18
19 #include "canonicalform.h"
20 #include "cf_primes.h"
21 #include "cf_util.h"
22 #include "cf_assert.h"
23
integerFactorizer(const long integer,int & length,bool & fail)24 int* integerFactorizer (const long integer, int& length, bool& fail)
25 {
26 ASSERT (integer != 0 && integer != 1 && integer != -1,
27 "non-zero non-unit expected");
28 int* result=NULL;
29 length= 0;
30 fail= false;
31 int i= integer;
32 if (integer < 0)
33 i = -integer;
34
35 int exp= 0;
36 while ((i != 1) && (i%2 == 0))
37 {
38 i /= 2;
39 exp++;
40 }
41 if (exp != 0)
42 {
43 result= new int [exp];
44 for (int k= 0; k < exp; k++)
45 result[k]= 2;
46 length += exp;
47 }
48 if (i == 1) return result;
49
50 long j= 0;
51 exp= 0;
52 int next_prime;
53 while ((i != 1) && (j < 31937))
54 {
55 next_prime= cf_getPrime (j);
56 while ((i != 1) && (i%next_prime == 0))
57 {
58 i /= next_prime;
59 exp++;
60 }
61 if (exp != 0)
62 {
63 int *buf= result;
64 result= new int [length + exp];
65 for (int k= 0; k < length; k++)
66 result [k]= buf[k];
67 for (int k= 0; k < exp; k++)
68 result [k + length]= next_prime;
69 length += exp;
70 delete[] buf;
71 }
72 exp= 0;
73 j++;
74 }
75 if (j >= 31397)
76 fail= true;
77 ASSERT (j < 31397, "integer factorizer ran out of primes"); //sic
78 return result;
79 }
80
81 /// make prime factorization distinct
82 static inline
makeDistinct(int * factors,const int factors_length,int & length)83 int* makeDistinct (int* factors, const int factors_length, int& length)
84 {
85 length= 1;
86 int* result= new int [length];
87 result[0]= factors [0];
88 for (int i= 1; i < factors_length; i++)
89 {
90 if (factors[i - 1] != factors[i])
91 {
92 int *buf= result;
93 result= new int [length + 1];
94 for (int j= 0; j < length; j++)
95 result[j]= buf [j];
96 result[length]= factors[i];
97 delete[] buf;
98 length++;
99 }
100 }
101 return result;
102 }
103
cyclotomicPoly(int n,bool & fail)104 CanonicalForm cyclotomicPoly (int n, bool& fail)
105 {
106 fail= false;
107 Variable x= Variable (1);
108 CanonicalForm result= x - 1;
109 if (n == 1)
110 return result;
111 int* prime_factors;
112 int prime_factors_length;
113 int distinct_factors_length;
114 prime_factors= integerFactorizer (n, prime_factors_length, fail);
115 int* distinct_factors= makeDistinct (prime_factors, prime_factors_length,
116 distinct_factors_length);
117 delete [] prime_factors;
118 if (fail)
119 return 1;
120 CanonicalForm buf;
121 int prod= 1;
122 for (int i= 0; i < distinct_factors_length; i++)
123 {
124 result= leftShift (result, distinct_factors[i])/result;
125 prod *= distinct_factors[i];
126 }
127 delete [] distinct_factors;
128 return leftShift (result, n/prod);
129 }
130
isPrimitive(const Variable & alpha,bool & fail)131 bool isPrimitive (const Variable& alpha, bool& fail)
132 {
133 int p= getCharacteristic();
134 CanonicalForm mipo= getMipo (alpha);
135 int order= ipower(p, degree(mipo)) - 1;
136 CanonicalForm cyclo= cyclotomicPoly (order, fail);
137 if (fail)
138 return false;
139 if (mod(cyclo, mipo (Variable(1), alpha)) == 0)
140 return true;
141 else
142 return false;
143 }
144