view release on metacpan or  search on metacpan

lib/Math/GF.pm  view on Meta::CPAN

   my @coeffs;
   while ($x) {
      push @coeffs, $x % $n;
      $x = ($x - $coeffs[-1]) / $n;
   }
   push @coeffs, 0 unless @coeffs;
   return Z_poly($n, @coeffs);
}

sub __rabin_irreducibility_test {
   my $f    = shift;
   my $n    = $f->degree;
   my $one  = $f->coeff_one;
   my $pone = Math::Polynomial->monomial(0, $one);
   my $x    = Math::Polynomial->monomial(1, $one);
   my $q    = $one->n;
   my $ps   = __prime_divisors_of($n);

   for my $pi (@$ps) {
      my $ni  = $n / $pi;
      my $qni = $q**$ni;
      my $h = (Math::Polynomial->monomial($qni, $one) - $x) % $f;
      my $g = $h->gcd($f, 'mod');
      #return if $g != $pone;
      return if $g->degree > 1;
   } ## end for my $pi (@$ps)
   my $t = (Math::Polynomial->monomial($q**$n, $one) - $x) % $f;
   return $t->degree == -1;
} ## end sub rabin_irreducibility_test

sub __prime_power_decomposition {
   my $x = shift;
   return if $x < 2;
   return ($x, 1) if $x < 4;

   my $p = __prime_divisors_of($x, 'first only please');
   return ($x, 1) if $x == $p;    # $x is prime

   my $e = 0;
   while ($x > 1) {
      return if $x % $p;         # not the only divisor!
      $x /= $p;
      ++$e;
   }
   return ($p, $e);
} ## end sub __prime_power_decomposition

sub __prime_divisors_of {
   my ($n, $first_only) = @_;
   my @retval;

   return if $n < 2;

   for my $p (2, 3) { # handle cases for 2 and 3 first
      next if $n % $p;
      return $p if $first_only;
      push @retval, $p;
      $n /= $p until $n % $p;
   }

   my $p = 5; # tentative divisor, will increase through iterations
   my $top = int(sqrt($n) + MARGIN); # top attempt for divisor
   my $d = 2; # increase for $p, alternates between 4 and 2
   while ($p <= $top) {
      if ($n % $p == 0) {
         return $p if $first_only;
         unshift @retval, $p;
         $n /= $p until $n % $p;
         $top = int(sqrt($n) + MARGIN);
      }
      $p += $d;
      $d = ($d == 2) ? 4 : 2;
   } ## end while ($n > 1)

   # exited with $n left as a prime... maybe
   return $n if $first_only; # always in this case
   push @retval, $n if $n > 1;

   return \@retval;
} ## end sub prime_divisors_of

1;