This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.37 in repository libmath-prime-util-perl.
commit 71a3bd117cfaa9adf335777a2b04e0dc848fbea6 Author: Dana Jacobsen <d...@acm.org> Date: Fri Jan 24 12:36:25 2014 -0800 znlog update --- Changes | 2 ++ TODO | 2 +- XS.xs | 4 ++-- factor.c | 8 ++++---- lib/Math/Prime/Util.pm | 7 +++++-- lib/Math/Prime/Util/PP.pm | 8 ++++---- t/81-bignum.t | 5 ++++- util.c | 11 +++++------ 8 files changed, 27 insertions(+), 20 deletions(-) diff --git a/Changes b/Changes index 1513dee..677bc6c 100644 --- a/Changes +++ b/Changes @@ -28,6 +28,8 @@ Revision history for Perl module Math::Prime::Util - nth_prime_{lower,upper,approx} and prime_count_{lower,upper,approx} moved to XS->PP. This helps us slim down and cut startup overhead. + - Fix doc for znlog: znlog(a,g,p) finds k s.t. a = g^k mod p + 0.36 2014-01-13 diff --git a/TODO b/TODO index 04f4d03..904b6ca 100644 --- a/TODO +++ b/TODO @@ -73,4 +73,4 @@ - Ensure a fast path for Math::GMP from MPU -> MPU:GMP -> GMP, and back. -- znlog bignum tests, znlog better implementation +- znlog better implementation diff --git a/XS.xs b/XS.xs index a7ccee5..e17bf86 100644 --- a/XS.xs +++ b/XS.xs @@ -739,7 +739,7 @@ znorder(IN SV* sva, IN SV* svn) } overflow: switch (ix) { - case 0: _vcallsub_with_pp("znorder"); break; + case 0: _vcallsub_with_gmp("znorder"); break; case 1: _vcallsub_with_pp("jordan_totient"); break; case 2: default: _vcallsub_with_pp("legendre_phi"); break; @@ -760,7 +760,7 @@ znlog(IN SV* sva, IN SV* svg, IN SV* svp) if (ret == 0 && a > 1) XSRETURN_UNDEF; XSRETURN_UV(ret); } - _vcallsub_with_pp("znlog"); + _vcallsub_with_gmp("znlog"); return; /* skip implicit PUTBACK */ void diff --git a/factor.c b/factor.c index 9ae66b1..752ab51 100644 --- a/factor.c +++ b/factor.c @@ -908,12 +908,12 @@ int squfof_factor(UV n, UV *factors, UV rounds) } UV dlp_trial(UV a, UV g, UV p, UV maxrounds) { - UV t, n = 1; + UV t, k = 1; if (maxrounds > p) maxrounds = p; - for (n = 1; n < maxrounds; n++) { - t = powmod(g, n, p); + for (k = 1; k < maxrounds; k++) { + t = powmod(g, k, p); if (t == a) - return n; + return k; } return 0; } diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index 1f3fb63..6e96795 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -499,6 +499,9 @@ sub prime_iterator { $start = 0 unless defined $start; _validate_num($start) || _validate_positive_integer($start); my $p = ($start > 0) ? $start-1 : 0; + # This works fine: + # return sub { $p = next_prime($p); return $p; }; + # but we can optimize a little if (ref($p) ne 'Math::BigInt' && $p <= $_XS_MAXVAL) { return sub { $p = next_prime($p); return $p; }; } elsif ($_HAVE_GMP) { @@ -2079,9 +2082,9 @@ produces. =head2 znlog - $k = znlog($b, $g, $p) + $k = znlog($a, $g, $p) -Returns the integer C<k> that solves the equation C<b^k = g mod p>, or +Returns the integer C<k> that solves the equation C<a = g^k 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. diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm index 461e767..e1601df 100644 --- a/lib/Math/Prime/Util/PP.pm +++ b/lib/Math/Prime/Util/PP.pm @@ -1695,11 +1695,11 @@ sub znorder { sub znlog { my ($a,$g,$p) = map { ref($_) eq 'Math::BigInt' ? $_ : Math::BigInt->new("$_") } @_; - for (my $n = BONE->copy; $n < $p; $n->binc) { - my $t = $g->copy->bmodpow($n, $p); + for (my $k = BONE->copy; $k < $p; $k->binc) { + my $t = $g->copy->bmodpow($k, $p); if ($t == $a) { - $n = _bigint_to_int($n) if $n->bacmp(''.~0) <= 0; - return $n; + $k = _bigint_to_int($k) if $k->bacmp(''.~0) <= 0; + return $k; } } return; diff --git a/t/81-bignum.t b/t/81-bignum.t index 0e064cf..e27564b 100644 --- a/t/81-bignum.t +++ b/t/81-bignum.t @@ -76,7 +76,7 @@ plan tests => 0 + 6*2*$extra # more PC tests + 2*scalar(keys %factors) + scalar(keys %allfactors) - + 13+3*$extra # moebius, euler_phi, jordan totient, divsum, etc. + + 14+3*$extra # moebius, euler_phi, jordan totient, divsum, etc. + 2 # liouville + 3 # gcd + 3 # lcm @@ -108,6 +108,7 @@ use Math::Prime::Util qw/ divisor_sum znorder znprimroot + znlog liouville gcd lcm @@ -267,6 +268,8 @@ SKIP: { is( znprimroot(333822190384002421914469856494764513809), 3, "znprimroot(333822190384002421914469856494764513809)" ); + is( znlog(232752345212475230211680, 23847293847923847239847098123812075234, 804842536444911030681947), 13, "znlog(b,g,p): find k where b^k = g mod p" ); + } ############################################################################### diff --git a/util.c b/util.c index 870581f..2dbae67 100644 --- a/util.c +++ b/util.c @@ -1220,9 +1220,9 @@ UV divmod(UV a, UV b, UV n) { /* a / b mod n */ return mulmod(a, binv, n); } -/* Find smallest n where a = g^n mod p +/* Find smallest k where a = g^k mod p * This implementation is just a stupid placeholder. - * When prho or bsgs gets working well, lower the trial limit + * When prho or bsgs starts working well, lower the trial limit */ #define DLP_TRIAL_NUM 1000000 UV znlog(UV a, UV g, UV p) { @@ -1399,10 +1399,9 @@ long double _XS_LogarithmicIntegral(long double x) { /* Thanks to Kim Walisch for this idea */ UV _XS_Inverse_Li(UV x) { - double n = x; - double logn = log(n); - UV lo = (UV) (n*logn); - UV hi = (UV) (n*logn * 2 + 2); + double nlogn = (double)x * log((double)x); + UV lo = (UV) (nlogn); + UV hi = (UV) (nlogn * 2 + 2); if (x == 0) return 0; if (hi <= lo) hi = UV_MAX; -- 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