[libmath-prime-util-perl] 128/181: First cut znlog

[Partha P. Mukherjee]

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 9c98f1b2182b5d81873ffe85175805aa6cd13f50
Author: Dana Jacobsen <d...@acm.org>
Date:   Tue Jan 7 01:42:29 2014 -0800

    First cut znlog
---
 XS.xs                  | 19 ++++++++++++++++++-
 lib/Math/Prime/Util.pm |  2 +-
 util.c                 | 12 ++++++++++++
 util.h                 |  1 +
 4 files changed, 32 insertions(+), 2 deletions(-)

diff --git a/XS.xs b/XS.xs
index 68c729f..2868381 100644
--- a/XS.xs
+++ b/XS.xs
@@ -115,7 +115,8 @@ static int _validate_int(pTHX_ SV* n, int negok)
   }
   if (SvROK(n)) {
     if (sv_isa(n, "Math::BigInt") || sv_isa(n, "Math::BigFloat") ||
-        sv_isa(n, "Math::GMP") || sv_isa(n, "Math::GMPz") )
+        sv_isa(n, "Math::Pari") || sv_isa(n, "Math::GMP") ||
+        sv_isa(n, "Math::GMPz") )
       isbignum = 1;
     else
       return 0;
@@ -668,6 +669,22 @@ znorder(IN SV* sva, IN SV* svn)
     return; /* skip implicit PUTBACK */
 
 void
+znlog(IN SV* sva, IN SV* svg, IN SV* svp)
+  PREINIT:
+    int astatus, gstatus, pstatus;
+  PPCODE:
+    astatus = _validate_int(aTHX_ sva, 0);
+    gstatus = _validate_int(aTHX_ svg, 0);
+    pstatus = _validate_int(aTHX_ svp, 0);
+    if (astatus == 1 && gstatus == 1 && pstatus == 1) {
+      UV ret = znlog(my_svuv(sva), my_svuv(svg), my_svuv(svp));
+      if (ret == 0) XSRETURN_UNDEF;
+      XSRETURN_UV(ret);
+    }
+    _vcallsub("PP::znlog");
+    return; /* skip implicit PUTBACK */
+
+void
 kronecker(IN SV* sva, IN SV* svb)
   PREINIT:
     int astatus, bstatus, abpositive, abnegative;
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 906fcd6..330c5fb 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -42,7 +42,7 @@ our @EXPORT_OK =
       partitions
       chebyshev_theta chebyshev_psi
       divisor_sum
-      carmichael_lambda kronecker znorder znprimroot legendre_phi
+      carmichael_lambda kronecker znorder znprimroot znlog legendre_phi
       ExponentialIntegral LogarithmicIntegral RiemannZeta RiemannR
   );
 our %EXPORT_TAGS = (all => [ @EXPORT_OK ]);
diff --git a/util.c b/util.c
index 6d1f225..b81cb66 100644
--- a/util.c
+++ b/util.c
@@ -1058,6 +1058,18 @@ UV znprimroot(UV n) {
   return 0;
 }
 
+/* Find smallest n where a = g^n mod p */
+/* This implementation is just a stupid placeholder. */
+UV znlog(UV a, UV g, UV p) {
+  UV t, n = 1;
+  if (a == 0 || g == 0 || p < 2) return 0;
+  for (n = 1; n < p; n++) {
+    t = powmod(g, n, p);
+    if (t == a)
+      return n;
+  }
+  return 0;
+}
 
 double _XS_chebyshev_theta(UV n)
 {
diff --git a/util.h b/util.h
index 3c048df..7c71493 100644
--- a/util.h
+++ b/util.h
@@ -37,6 +37,7 @@ extern UV exp_mangoldt(UV n);
 extern UV carmichael_lambda(UV n);
 extern UV znprimroot(UV n);
 extern UV znorder(UV a, UV n);
+extern UV znlog(UV a, UV g, UV p);
 
 /* Above this value, is_prime will do deterministic Miller-Rabin */
 /* With 64-bit math, we can do much faster mulmods from 2^16-2^32 */

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