My Project  UNKNOWN_GIT_VERSION
cf_cyclo.cc
Go to the documentation of this file.
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 
24 #ifdef HAVE_NTL
25 #include <NTL/ZZ.h>
26 #endif
27 
28 int* integerFactorizer (const long integer, int& length, bool& fail)
29 {
30  ASSERT (integer != 0 && integer != 1 && integer != -1,
31  "non-zero non-unit expected");
32  int* result=NULL;
33  length= 0;
34  fail= false;
35  int i= integer;
36  if (integer < 0)
37  i = -integer;
38 
39  int exp= 0;
40  while ((i != 1) && (i%2 == 0))
41  {
42  i /= 2;
43  exp++;
44  }
45  if (exp != 0)
46  {
47  result= new int [exp];
48  for (int k= 0; k < exp; k++)
49  result[k]= 2;
50  length += exp;
51  }
52  if (i == 1) return result;
53 
54  long j= 0;
55  exp= 0;
56  int next_prime;
57  while ((i != 1) && (j < 31937))
58  {
59  next_prime= cf_getPrime (j);
60  while ((i != 1) && (i%next_prime == 0))
61  {
62  i /= next_prime;
63  exp++;
64  }
65  if (exp != 0)
66  {
67  int *buf= result;
68  result= new int [length + exp];
69  for (int k= 0; k < length; k++)
70  result [k]= buf[k];
71  for (int k= 0; k < exp; k++)
72  result [k + length]= next_prime;
73  length += exp;
74  delete[] buf;
75  }
76  exp= 0;
77  j++;
78  }
79  if (j >= 31397)
80  fail= true;
81  ASSERT (j < 31397, "integer factorizer ran out of primes"); //sic
82  return result;
83 }
84 
85 /// make prime factorization distinct
86 static inline
87 int* makeDistinct (int* factors, const int factors_length, int& length)
88 {
89  length= 1;
90  int* result= new int [length];
91  result[0]= factors [0];
92  for (int i= 1; i < factors_length; i++)
93  {
94  if (factors[i - 1] != factors[i])
95  {
96  int *buf= result;
97  result= new int [length + 1];
98  for (int j= 0; j < length; j++)
99  result[j]= buf [j];
100  result[length]= factors[i];
101  delete[] buf;
102  length++;
103  }
104  }
105  return result;
106 }
107 
108 CanonicalForm cyclotomicPoly (int n, bool& fail)
109 {
110  fail= false;
111  Variable x= Variable (1);
112  CanonicalForm result= x - 1;
113  if (n == 1)
114  return result;
115  int* prime_factors;
116  int prime_factors_length;
117  int distinct_factors_length;
118  prime_factors= integerFactorizer (n, prime_factors_length, fail);
119  int* distinct_factors= makeDistinct (prime_factors, prime_factors_length,
120  distinct_factors_length);
121  delete [] prime_factors;
122  if (fail)
123  return 1;
125  int prod= 1;
126  for (int i= 0; i < distinct_factors_length; i++)
127  {
128  result= leftShift (result, distinct_factors[i])/result;
129  prod *= distinct_factors[i];
130  }
131  delete [] distinct_factors;
132  return leftShift (result, n/prod);
133 }
134 
135 #ifdef HAVE_NTL
136 bool isPrimitive (const Variable& alpha, bool& fail)
137 {
138  int p= getCharacteristic();
140  int order= ipower(p, degree(mipo)) - 1;
141  CanonicalForm cyclo= cyclotomicPoly (order, fail);
142  if (fail)
143  return false;
144  if (mod(cyclo, mipo (Variable(1), alpha)) == 0)
145  return true;
146  else
147  return false;
148 }
149 
150 #endif
j
int j
Definition: facHensel.cc:105
k
int k
Definition: cfEzgcd.cc:92
canonicalform.h
x
Variable x
Definition: cfModGcd.cc:4023
result
return result
Definition: facAbsBiFact.cc:76
prod
fq_nmod_poly_t prod
Definition: facHensel.cc:95
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
cf_primes.h
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
makeDistinct
static int * makeDistinct(int *factors, const int factors_length, int &length)
make prime factorization distinct
Definition: cf_cyclo.cc:87
cyclotomicPoly
CanonicalForm cyclotomicPoly(int n, bool &fail)
compute the n-th cyclotomic polynomial, function may fail if integer_factorizer fails to factorize n
Definition: cf_cyclo.cc:108
CanonicalForm
factory's main class
Definition: canonicalform.h:77
i
int i
Definition: cfEzgcd.cc:125
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
buf
int status int void * buf
Definition: si_signals.h:59
isPrimitive
bool isPrimitive(const Variable &alpha, bool &fail)
checks if alpha is a primitive element, alpha is assumed to be an algebraic variable over some finite...
Definition: cf_cyclo.cc:136
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
cf_util.h
cf_getPrime
int cf_getPrime(int i)
Definition: cf_primes.cc:14
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
exp
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:358
integerFactorizer
int * integerFactorizer(const long integer, int &length, bool &fail)
integer factorization using table look-ups, function may fail if integer contains primes which exceed...
Definition: cf_cyclo.cc:28
leftShift
CanonicalForm leftShift(const CanonicalForm &F, int n)
left shift the main variable of F by n
Definition: cf_ops.cc:683
Variable
factory's class for variables
Definition: factory.h:117
NULL
#define NULL
Definition: omList.c:10
cf_assert.h
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309