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