Functions
cf_cyclo.cc File Reference

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

#include "config.h"
#include "canonicalform.h"
#include "cf_primes.h"
#include "cf_util.h"
#include "cf_assert.h"
#include <NTL/ZZ.h>

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...
 
static int * makeDistinct (int *factors, const int factors_length, int &length)
 make prime factorization distinct 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
Date
29.01.2010

Definition in file cf_cyclo.cc.

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  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 }
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
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
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
return result
Definition: facAbsBiFact.cc:76

◆ 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* 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 }
int cf_getPrime(int i)
Definition: cf_primes.cc:14
int k
Definition: cfEzgcd.cc:93
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:123
#define NULL
Definition: omList.c:10
#define ASSERT(expression, message)
Definition: cf_assert.h:99
p exp[i]
Definition: DebugPrint.cc:39
return result
Definition: facAbsBiFact.cc:76

◆ 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 134 of file cf_cyclo.cc.

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 }
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
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 ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
CanonicalForm mipo
Definition: facAlgExt.cc:57
int degree(const CanonicalForm &f)

◆ makeDistinct()

static int* makeDistinct ( int *  factors,
const int  factors_length,
int &  length 
)
inlinestatic

make prime factorization distinct

Definition at line 87 of file cf_cyclo.cc.

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 }
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:123
return result
Definition: facAbsBiFact.cc:76