facIrredTest.h File Reference

This file provides a probabilistic irreducibility test for polynomials over Z/p. More...

#include "canonicalform.h"

Go to the source code of this file.

Functions
double	numZeros (const CanonicalForm &F, int k)
	evaluate F at k random points in Z/p^n and count the number of zeros that occur More...
int FACTORY_PUBLIC	probIrredTest (const CanonicalForm &F, double error)
	given some error probIrredTest detects irreducibility or reducibility of F with confidence level 1-error More...

Detailed Description

This file provides a probabilistic irreducibility test for polynomials over Z/p.

ABSTRACT: irreducibility test based on "Quick and Dirty Irreducibility Test" by v. Bothmer and Schreyer

Author

Martin Lee

Definition in file facIrredTest.h.

Function Documentation

numZeros()

double numZeros	(	const CanonicalForm &	F,
		int	k
	)

evaluate F at k random points in Z/p^n and count the number of zeros that occur

Returns

numZeros returns #zeros/trials

Parameters

[in]	F	some poly over Z/p with n variables
[in]	k	number of trials

Definition at line 24 of file facIrredTest.cc.

{
  int result= 0;
 
  FFRandom FFgen;
  CanonicalForm buf;
  for (int i= 0; i < k; i++)
  {
    buf= F;
    for (int j= F.level(); j > 0; j++)
      buf= buf (FFgen.generate(), j);
    if (buf.isZero())
      result++;
  }
 
  return (double) result/k;
}

probIrredTest()

int FACTORY_PUBLIC probIrredTest	(	const CanonicalForm &	F,
		double	error
	)

given some error probIrredTest detects irreducibility or reducibility of F with confidence level 1-error

Returns

probIrredTest returns 1 for irreducibility, -1 for reducibility or 0 if the test is not applicable

Parameters

[in]	F	some poly over Z/p
[in]	error	0 < error < 1

Definition at line 63 of file facIrredTest.cc.

{
  CFMap N;
  CanonicalForm G= compress (F, N);
  int n= G.level();
  int p= getCharacteristic();
 
  double sqrtTrials= inverseERF (1-2.0*error)*sqrt (2.0);
 
  double s= sqrtTrials;
 
  double pn= pow ((double) p, (double) n);
  double p1= (double) 1/p;
  p1= p1*(1.0-p1);
  p1= p1/(double) pn;
  p1= sqrt (p1);
  p1 *= s;
  p1 += (double) 1/p;
 
  double p2= (double) (2*p-1)/(p*p);
  p2= p2*(1-p2);
  p2= p2/(double) pn;
  p2= sqrt (p2);
  p2 *= s;
  p2= (double) (2*p - 1)/(p*p)-p2;
 
  //no testing possible
  if (p2 < p1)
    return 0;
 
  double den= sqrt (p1*(1-p1))+sqrt (p2*(1-p2));
  double num= p2-p1;
 
  sqrtTrials *= den/num;
 
  int trials= (int) floor (pow (sqrtTrials, 2.0));
 
  double experimentalNumZeros= numZeros (G, trials);
 
  double pmiddle= sqrt (p1*p2);
 
  num= den;
  den= sqrt (p1*(1.0-p2))+sqrt (p2*(1.0-p1));
  pmiddle *= (den/num);
 
  if (experimentalNumZeros < pmiddle)
    return 1;
  else
    return -1;
}