My Project
Loading...
Searching...
No Matches
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"

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
 
static int * makeDistinct (int *factors, const int factors_length, int &length)
 make prime factorization distinct
 
CanonicalForm cyclotomicPoly (int n, bool &fail)
 compute the n-th cyclotomic polynomial, function may fail if integer_factorizer fails to factorize n
 
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
 

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
fail[in,out] failure?

Definition at line 104 of file cf_cyclo.cc.

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

◆ 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
length[in,out] number of factors
fail[in,out] failure?

Definition at line 24 of file cf_cyclo.cc.

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

◆ 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
fail[in,out] failure?

Definition at line 131 of file cf_cyclo.cc.

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}
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 p
Definition cfModGcd.cc:4086
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
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
Variable alpha
CanonicalForm mipo
Definition facAlgExt.cc:57
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207

◆ makeDistinct()

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

make prime factorization distinct

Definition at line 83 of file cf_cyclo.cc.

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}