znorder(a,n): optimization for large n with many small factors.

[trizen]

Currently, when n is large and has many small prime factors, znorder(a,n) is quite slow, but it can be made much faster by using the following identity:

znorder($a,$n) == lcm(map { znorder($a, powint($_->[0], $_->[1])) } factor_exp($n));

Example:

use 5.014;
use Math::Prime::Util::GMP qw(:all);
use Time::HiRes qw(gettimeofday tv_interval);

my $a = 10007;
my $n = factorial(1000);

my $t0 = [gettimeofday];
my $x  = znorder($a, $n);
say "znorder(a,n) took: ", tv_interval($t0), ' seconds';

my $t1 = [gettimeofday];
my %factors; ++$factors{$_} for factor($n);
my $y  = lcm(map { znorder($a, powint($_, $factors{$_})) } keys %factors);
say "lcm(znorder(a, p^e)) took: ", tv_interval($t1), ' seconds';

$x eq $y or die "error: x != y";

Output:

znorder(a,n) took: 11.648454 seconds
lcm(znorder(a, p^e)) took: 0.006773 seconds

[danaj]

Was:

  $ make >/dev/null && perl -Iblib/lib -Iblib/arch ~/tmp/znorder-lcm.pl
  znorder(a,n) took: 6.134748 seconds
  lcm(znorder(a, p^e)) took: 0.00322 seconds

Now (code not commited yet)

  $ make >/dev/null && perl -Iblib/lib -Iblib/arch ~/tmp/znorder-lcm.pl
  znorder(a,n) took: 0.002527 seconds
  lcm(znorder(a, p^e)) took: 0.00324 seconds