[libmath-prime-util-perl] 47/181: Switch znorder to factoring Carmichael Lambda

```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.