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

Definition at line 104 of file cf_cyclo.cc.

{
  fail= false;
  Variable x= Variable (1);
  CanonicalForm result= x - 1;
  if (n == 1)
    return result;
  int* prime_factors;
  int prime_factors_length;
  int distinct_factors_length;
  prime_factors= integerFactorizer (n, prime_factors_length, fail);
  int* distinct_factors= makeDistinct (prime_factors, prime_factors_length,
                                        distinct_factors_length);
  delete [] prime_factors;
  if (fail)
    return 1;
  CanonicalForm buf;
  int prod= 1;
  for (int i= 0; i < distinct_factors_length; i++)
  {
    result= leftShift (result, distinct_factors[i])/result;
    prod *= distinct_factors[i];
  }
  delete [] distinct_factors;
  return leftShift (result, n/prod);
}

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

Definition at line 24 of file cf_cyclo.cc.

{
  ASSERT (integer != 0 && integer != 1 && integer != -1,
          "non-zero non-unit expected");
  int* result=NULL;
  length= 0;
  fail= false;
  int i= integer;
  if (integer < 0)
    i = -integer;
 
  int exp= 0;
  while ((i != 1) && (i%2 == 0))
  {
    i /= 2;
    exp++;
  }
  if (exp != 0)
  {
    result= new int [exp];
    for (int k= 0; k < exp; k++)
      result[k]= 2;
    length += exp;
  }
  if (i == 1) return result;
 
  long j= 0;
  exp= 0;
  int next_prime;
  while ((i != 1) && (j < 31937))
  {
    next_prime= cf_getPrime (j);
    while ((i != 1) && (i%next_prime == 0))
    {
      i /= next_prime;
      exp++;
    }
    if (exp != 0)
    {
      int *buf= result;
      result= new int [length + exp];
      for (int k= 0; k < length; k++)
        result [k]= buf[k];
      for (int k= 0; k < exp; k++)
        result [k + length]= next_prime;
      length += exp;
      delete[] buf;
    }
    exp= 0;
    j++;
  }
  if (j >= 31397)
    fail= true;
  ASSERT (j < 31397, "integer factorizer ran out of primes"); //sic
  return result;
}

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

Definition at line 131 of file cf_cyclo.cc.

{
  int p= getCharacteristic();
  CanonicalForm mipo= getMipo (alpha);
  int order= ipower(p, degree(mipo)) - 1;
  CanonicalForm cyclo= cyclotomicPoly (order, fail);
  if (fail)
    return false;
  if (mod(cyclo, mipo (Variable(1), alpha)) == 0)
    return true;
  else
    return false;
}

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.

{
  length= 1;
  int* result= new int [length];
  result[0]= factors [0];
  for (int i= 1; i < factors_length; i++)
  {
    if (factors[i - 1] != factors[i])
    {
      int *buf= result;
      result= new int [length + 1];
      for (int j= 0; j < length; j++)
        result[j]= buf [j];
      result[length]= factors[i];
      delete[] buf;
      length++;
    }
  }
  return result;
}