My Project
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 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
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 
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;
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 
131 bool isPrimitive (const Variable& alpha, bool& fail)
132 {
133  int p= getCharacteristic();
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 }
Header for factory's main class CanonicalForm.
CanonicalForm leftShift(const CanonicalForm &F, int n)
left shift the main variable of F by n
Definition: cf_ops.cc:697
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
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:104
static int * makeDistinct(int *factors, const int factors_length, int &length)
make prime factorization distinct
Definition: cf_cyclo.cc:83
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:24
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:131
int cf_getPrime(int i)
Definition: cf_primes.cc:14
access to prime tables
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
factory's main class
Definition: canonicalform.h:86
factory's class for variables
Definition: factory.h:127
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
CanonicalForm mipo
Definition: facAlgExt.cc:57
int j
Definition: facHensel.cc:110
fq_nmod_poly_t prod
Definition: facHensel.cc:100
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
#define NULL
Definition: omList.c:12
int status int void * buf
Definition: si_signals.h:59