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* buf;
57  int next_prime;
58  while ((i != 1) && (j < 31937))
59  {
60  next_prime= cf_getPrime (j);
61  while ((i != 1) && (i%next_prime == 0))
62  {
63  i /= next_prime;
64  exp++;
65  }
66  if (exp != 0)
67  {
68  buf= result;
69  result= new int [length + exp];
70  for (int k= 0; k < length; k++)
71  result [k]= buf[k];
72  for (int k= 0; k < exp; k++)
73  result [k + length]= next_prime;
74  length += exp;
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  int* buf;
92  result[0]= factors [0];
93  for (int i= 1; i < factors_length; i++)
94  {
95  if (factors[i - 1] != factors[i])
96  {
97  buf= result;
98  result= new int [length + 1];
99  for (int j= 0; j < length; j++)
100  result[j]= buf [j];
101  result[length]= factors[i];
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  if (fail)
122  return 1;
124  int prod= 1;
125  for (int i= 0; i < distinct_factors_length; i++)
126  {
127  result= leftShift (result, distinct_factors[i])/result;
128  prod *= distinct_factors[i];
129  }
130  return leftShift (result, n/prod);
131 }
132 
133 #ifdef HAVE_NTL
134 bool isPrimitive (const Variable& alpha, bool& fail)
135 {
136  int p= getCharacteristic();
137  CanonicalForm mipo= getMipo (alpha);
138  int order= ipower(p, degree(mipo)) - 1;
139  CanonicalForm cyclo= cyclotomicPoly (order, fail);
140  if (fail)
141  return false;
142  if (mod(cyclo, mipo (Variable(1), alpha)) == 0)
143  return true;
144  else
145  return false;
146 }
147 
148 #endif
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
int cf_getPrime(int i)
Definition: cf_primes.cc:14
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
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:134
factory&#39;s main class
Definition: canonicalform.h:75
assertions for Factory
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
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
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:123
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
#define NULL
Definition: omList.c:10
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
access to prime tables
CanonicalForm leftShift(const CanonicalForm &F, int n)
left shift the main variable of F by n
Definition: cf_ops.cc:683
fq_nmod_poly_t prod
Definition: facHensel.cc:95
static int * makeDistinct(int *factors, const int factors_length, int &length)
make prime factorization distinct
Definition: cf_cyclo.cc:87
Variable x
Definition: cfModGcd.cc:4023
#define ASSERT(expression, message)
Definition: cf_assert.h:99
p exp[i]
Definition: DebugPrint.cc:39
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
Header for factory&#39;s main class CanonicalForm.