My Project  UNKNOWN_GIT_VERSION
Functions
cf_cyclo.h File Reference

Compute cyclotomic polynomials and factorize integers by brute force. More...

Go to the source code of this file.

Functions

int * integerFactorizer (const long integer, int &length, bool &fail)
 integer factorization using table look-ups, function may fail if integer contains primes which exceed the largest prime in our table More...
 
CanonicalForm cyclotomicPoly (int n, bool &fail)
 compute the n-th cyclotomic polynomial, function may fail if integer_factorizer fails to factorize n More...
 
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 prime field More...
 

Detailed Description

Compute cyclotomic polynomials and factorize integers by brute force.

Copyright:
(c) by The SINGULAR Team, see LICENSE file
Author
Martin Lee

Definition in file cf_cyclo.h.

Function Documentation

◆ cyclotomicPoly()

CanonicalForm cyclotomicPoly ( int  n,
bool &  fail 
)

compute the n-th cyclotomic polynomial, function may fail if integer_factorizer fails to factorize n

Parameters
[in]nsome integer
[in,out]failfailure?

Definition at line 108 of file cf_cyclo.cc.

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 }
CanonicalForm leftShift(const CanonicalForm &F, int n)
left shift the main variable of F by n
Definition: cf_ops.cc:683
int i
Definition: cfEzgcd.cc:125
Variable x
Definition: cfModGcd.cc:4023
static int * makeDistinct(int *factors, const int factors_length, int &length)
make prime factorization distinct
Definition: cf_cyclo.cc:87
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
factory's main class
Definition: canonicalform.h:83
factory's class for variables
Definition: factory.h:118
return result
Definition: facAbsBiFact.cc:76
fq_nmod_poly_t prod
Definition: facHensel.cc:95
int status int void * buf
Definition: si_signals.h:59

◆ 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 the largest prime in our table

Parameters
[in]integersome integer
[in,out]lengthnumber of factors
[in,out]failfailure?

Definition at line 28 of file cf_cyclo.cc.

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 }
int k
Definition: cfEzgcd.cc:92
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int cf_getPrime(int i)
Definition: cf_primes.cc:14
int j
Definition: facHensel.cc:105
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:358
#define NULL
Definition: omList.c:10

◆ 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 prime field

Parameters
[in]alphasome algebraic variable
[in,out]failfailure?

Definition at line 136 of file cf_cyclo.cc.

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 }
int getCharacteristic()
Definition: cf_char.cc:51
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
int degree(const CanonicalForm &f)
int p
Definition: cfModGcd.cc:4019
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 ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm mipo
Definition: facAlgExt.cc:57
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207