My Project
Loading...
Searching...
No Matches
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
24int* 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
82static inline
83int* 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
104CanonicalForm cyclotomicPoly (int n, bool& fail)
105{
106 fail= false;
107 Variable x= Variable (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
131bool 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
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
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
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: variable.h:33
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
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
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207