This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.36 in repository libmath-prime-util-perl.
commit c07ebdea135f2032ca6760c44dc3ea22312535e9 Author: Dana Jacobsen <d...@acm.org> Date: Thu Dec 26 11:18:17 2013 -0800 Switch znorder to factoring Carmichael Lambda --- lib/Math/Prime/Util.pm | 33 ++++++++++++++++++--------------- 1 file changed, 18 insertions(+), 15 deletions(-) diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index c4cbf66..42b6b64 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -1687,19 +1687,28 @@ sub znorder { # Sadly, Calc/FastCalc are horrendously slow for this function. return if Math::BigInt::bgcd($a, $n) > 1; - # Method 1: check all a^k 1 .. $n-1. - # Naive and terrible slow. + # Method 1: check all a^k 1 .. $n-1. Naive and terrible slow. # Method 2: check all k in (divisors(euler_phi($n), $n). + # Much better, but slow with many divisors. # Method 3: check all k in (divisors(carmichael_lambda($n), $n). - # Good for most cases, but slow when factor quantity is large. - # Method 4: Das algorithm 1.7, just enough multiples of p - # Fastest. + # Stronger result, but still can have too many divisors. + # Method 4: Abhijit Das, alg 1.7, just enough multiples of p. + # Combine this with method 3. # # Most of the time is spent factoring $n and $phi. We could do the phi # construction here and build its factors to save a little more time. $a = Math::BigInt->new("$a") unless ref($a) eq 'Math::BigInt'; - my $phi = Math::BigInt->new('' . euler_phi($n)); + + # Method 3: + # foreach my $k (divisors(carmichael_lambda($n))) { + # return $k if $k != 1 && $a->copy->bmodpow("$k", $n)->is_one; + # } + # return; + + # Method 4 (Das algorithm 1.7 applied to Carmichael Lambda) + #my $phi = Math::BigInt->new('' . euler_phi($n)); + my $phi = Math::BigInt->new('' . carmichael_lambda($n)); my @pe = ($phi <= $_XS_MAXVAL) ? _XS_factor_exp($phi) : factor_exp($phi); my $k = Math::BigInt->bone; foreach my $f (@pe) { @@ -1714,14 +1723,6 @@ sub znorder { } $k = int($k->bstr) if $k->bacmp(''.~0) <= 0; return $k; - - # Method 3: - # my $cl = carmichael_lambda($n); - # foreach my $k (divisors($cl), $cl) { - # my $t = $a->copy->bmodpow("$k", $n); - # return $k if $t->is_one; - # } - # return; } @@ -3794,8 +3795,10 @@ This is L<OEIS series A002322|http://oeis.org/A002322>. Given two positive integers C<a> and C<n>, returns the multiplicative order of C<a> modulo <n>. This is the smallest positive integer C<k> such that -C<a^k ≡ 1 mod n>. Returns 1 if C<a = 1>. Return undef if C<a = 0> or if +C<a^k ≡ 1 mod n>. Returns 1 if C<a = 1>. Returns undef if C<a = 0> or if C<a> and C<n> are not coprime, since no value will result in 1 mod n. +This corresponds to Pari's C<znorder(Mod(a,n))> function and Mathematica's +C<MultiplicativeOrder[n]> function. =head2 random_prime -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git _______________________________________________ Pkg-perl-cvs-commits mailing list Pkg-perl-cvs-commits@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits