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 c62ac0deb6f51737537f0cc0a7624ff1b85232bf
Author: Dana Jacobsen <d...@acm.org>
Date: Thu Jan 9 00:34:07 2014 -0800
znlog tests and PP placeholder
---
lib/Math/Prime/Util.pm | 16 ++++++++++++++++
lib/Math/Prime/Util/PP.pm | 16 ++++++++++++++++
t/19-moebius.t | 23 ++++++++++++++++++++++-
3 files changed, 54 insertions(+), 1 deletion(-)
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index b263fbb..e10e6bc 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -118,6 +118,7 @@ BEGIN {
*divisor_sum = \&Math::Prime::Util::_generic_divisor_sum;
*znorder = \&Math::Prime::Util::PP::znorder;
*znprimroot = \&Math::Prime::Util::_generic_znprimroot;
+ *znlog = \&Math::Prime::Util::PP::znlog;
*legendre_phi = \&Math::Prime::Util::PP::legendre_phi;
*gcd = \&Math::Prime::Util::PP::gcd;
*lcm = \&Math::Prime::Util::PP::lcm;
@@ -1091,6 +1092,12 @@ sub primes {
}
print "*" if $verbose > 2;
+ # We could pick a random generator by doing:
+ # Step 1: pick a random r
+ # Step 2: compute g = r^((n-1)/q) mod p
+ # Step 3: if g == 1, goto Step 1.
+ # Note that n = 2*R*q+1, hence the exponent is 2*R.
+
# We could set r = 0.3333 earlier, then use BLS75 theorem 5 here.
# The chain would be shorter, requiring less overall work for
# large inputs. Maurer's paper discusses the idea.
@@ -3479,6 +3486,15 @@ the primitive root exists, while L<OEIS
A046145|http://oeis.org/A046145>
is a list of the smallest primitive roots, which is what this function
produces.
+=head2 znlog
+
+ $k = znlog($b, $g, $p)
+
+Returns the integer C<k> that solves the equation C<b^k = g mod p>, or
+undef if no solution is found. This is the discrete logarithm problem.
+The implementation in this version is not very useful, but may be improved.
+
+
=head2 legendre_phi
$phi = legendre_phi(1000000000, 41);
diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm
index 34ab778..1eaca36 100644
--- a/lib/Math/Prime/Util/PP.pm
+++ b/lib/Math/Prime/Util/PP.pm
@@ -1245,6 +1245,22 @@ sub znorder {
return $k;
}
+sub znlog {
+ my($a,$g,$p) = @_;
+ # This is just a stupid brute force search.
+ $a = Math::BigInt->new("$a") unless ref($a) eq 'Math::BigInt';
+ $g = Math::BigInt->new("$g") unless ref($g) eq 'Math::BigInt';
+ $p = Math::BigInt->new("$p") unless ref($p) eq 'Math::BigInt';
+ for (my $n = BONE->copy; $n < $p; $n->binc) {
+ my $t = $g->copy->bmodpow($n, $p);
+ if ($t == $a) {
+ $n = _bigint_to_int($n) if $n->bacmp(''.~0) <= 0;
+ return $n;
+ }
+ }
+ return;
+}
+
# Find first D in sequence (5,-7,9,-11,13,-15,...) where (D|N) == -1
sub _lucas_selfridge_params {
my($n) = @_;
diff --git a/t/19-moebius.t b/t/19-moebius.t
index 502cec8..dd56fe6 100644
--- a/t/19-moebius.t
+++ b/t/19-moebius.t
@@ -6,7 +6,7 @@ use Test::More;
use Math::Prime::Util
qw/moebius mertens euler_phi jordan_totient divisor_sum exp_mangoldt
chebyshev_theta chebyshev_psi carmichael_lambda znorder liouville
- znprimroot kronecker legendre_phi gcd lcm
+ znprimroot znlog kronecker legendre_phi gcd lcm
/;
my $extra = defined $ENV{EXTENDED_TESTING} && $ENV{EXTENDED_TESTING};
@@ -325,6 +325,19 @@ if ($use64) {
push @lcms, [ [267220708,143775143,261076], 15015659316963449908];
}
+my @znlogs = (
+ [ [5,2,1019], 10],
+ [ [2,4,17], undef],
+ [ [7,3,8], undef],
+ [ [3,3,8], 1],
+ [ [10,2,101], 25],
+ [ [2,55,101], 73], # 2 = 55^73 mod 101
+ [ [3061666278, 499998, 3332205179], 22],
+);
+if ($usexs) {
+ push @znlogs, [ [5678,5,10007], 8620]; # 5678 = 5^8620 mod 10007
+}
+
# These are slow with XS, and *really* slow with PP.
if (!$usexs) {
%big_mertens = map { $_ => $big_mertens{$_} }
@@ -355,6 +368,7 @@ plan tests => 0 + 1
+ scalar(@gcds)
+ scalar(@lcms)
+ scalar(@mult_orders)
+ + scalar(@znlogs)
+ scalar(@legendre_sums)
+ scalar(keys %primroots) + 2
+ scalar(keys %jordan_totients)
@@ -527,6 +541,13 @@ while (my($n, $root) = each (%primroots)) {
}
is( znprimroot("-100000898"), 31, "znprimroot(\"-100000898\") == 31" );
is( znprimroot("+100000898"), 31, "znprimroot(\"+100000898\") == 31" );
+###### znlog
+foreach my $arg (@znlogs) {
+ my($aref, $exp) = @$arg;
+ my ($a, $g, $p) = @$aref;
+ my $k = znlog($a,$g,$p);
+ is( $k, $exp, "znlog($a,$g,$p) = " . ((defined $exp) ? $exp : "<undef>") );
+}
###### liouville
foreach my $i (@liouville_pos) {
is( liouville($i), 1, "liouville($i) = 1" );
--
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
