This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.40 in repository libmath-prime-util-perl.

commit f74438fe6bdc0c3dfb3002e0aeed2db29251f2ae Author: Dana Jacobsen <d...@acm.org> Date: Tue Mar 4 18:53:58 2014 -0800 Documentation updates --- lib/Math/Prime/Util.pm | 221 ++++++++++++++++++++++++-------------------- t/92-release-pod-coverage.t | 2 + 2 files changed, 122 insertions(+), 101 deletions(-) diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index d9c2a10..ac134a3 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -47,6 +47,9 @@ our @EXPORT_OK = ); our %EXPORT_TAGS = (all => [ @EXPORT_OK ]); +# These are only exported if specifically asked for +push @EXPORT_OK, (qw/trial_factor fermat_factor holf_factor squfof_factor prho_factor pbrent_factor pminus1_factor pplus1_factor/); + my %_Config; # Similar to how boolean handles its option @@ -1356,10 +1359,6 @@ Returning composite for all non-2 even input makes the function match most other implementations including L<Math::Primality>'s C<is_strong_pseudoprime> function. -=head2 miller_rabin - -An alias for C<is_strong_pseudoprime>. This name is deprecated. - =head2 is_lucas_pseudoprime Takes a positive number as input, and returns 1 if the input is a standard @@ -1763,6 +1762,14 @@ literally B<millions> of times slower than other algorithms. From R.P. Brent, 2010: "AKS is not a practical algorithm. ECPP is much faster." We have ECPP, and indeed it is much faster. +This implementation includes the v6 improvements from Lenstra as well as +further improvements from Bernstein and Voloch. It runs substantially +faster than the original or v6 versions. The GMP implementation uses +a binary segmentation method for modular polynomial multiplication +(see Bernstein's 2007 Quartic paper), which reduces to a single scalar +multiplication, at which GMP excels. Because of this, the GMP +implementation is likely to be faster once the input is larger than C<2^32>. + =head2 is_power @@ -1776,10 +1783,10 @@ the largest possible. This can be used in a boolean statement to determine if C<n> is a perfect power. If given two arguments C<n> and C<k>, returns 1 if C<n> is a C<k-th> power, -and 0 otherwise. +and 0 otherwise. For example, if C<k=2> then this detects perfect squares. This corresponds to Pari/GP's C<ispower> function, with the limitations of -only integer arguments and no third argument may be given returning the root. +only integer arguments and no third argument may be given to return the root. =head2 lucas_sequence @@ -2053,29 +2060,31 @@ coprime to C<n>. This is L<OEIS series A002322|http://oeis.org/A002322>. =head2 kronecker Returns the Kronecker symbol C<(a|n)> for two integers. The possible -return values with their meanings for odd positive C<n> are: +return values with their meanings for odd prime C<n> are: 0 a = 0 mod n - 1 a is a quadratic residue modulo n (a = x^2 mod n for some x) - -1 a is a quadratic non-residue modulo n + 1 a is a quadratic residue mod n (a = x^2 mod n for some x) + -1 a is a quadratic non-residue mod n (no a where a = x^2 mod n) The Kronecker symbol is an extension of the Jacobi symbol to all integer values of C<n> from the latter's domain of positive odd values of C<n>. The Jacobi symbol is itself an extension of the Legendre symbol, which is only defined for odd prime values of C<n>. This corresponds to Pari's -C<kronecker(a,n)> function and Mathematica's C<KroneckerSymbol[n,m]> -function. +C<kronecker(a,n)> function, Mathematica's C<KroneckerSymbol[n,m]> +function, and GMP's C<mpz_kronecker(a,n)>, C<mpz_jacobi(a,n)>, and +C<mpz_legendre(a,n)> functions. + =head2 znorder - $order = znorder(2, next_prime(10**19)-6); + $order = znorder(2, next_prime(10**16)-6); Given two positive integers C<a> and C<n>, returns the multiplicative order of C<a> modulo C<n>. This is the smallest positive integer C<k> such that 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. +C<MultiplicativeOrder[a,n]> function. =head2 znprimroot @@ -2362,6 +2371,7 @@ in place because you still have an object. Returns a reference to a hash of the current settings. The hash is copy of the configuration, so changing it has no effect. The settings include: + verbose verbose level. 1 or more will result in extra output. precalc_to primes up to this number are calculated maxbits the maximum number of bits for native operations xs 0 or 1, indicating the XS code is available @@ -2378,26 +2388,35 @@ the configuration, so changing it has no effect. The settings include: Allows setting of some parameters. Currently the only parameters are: - xs Allows turning off the XS code, forcing the Pure Perl - code to be used. Set to 0 to disable XS, set to 1 to - re-enable. You probably will never want to do this. - - gmp Allows turning off the use of L<Math::Prime::Util::GMP>, - which means using Pure Perl code for big numbers. Set - to 0 to disable GMP, set to 1 to re-enable. - You probably will never want to do this. - - assume_rh Allows functions to assume the Riemann hypothesis is - true if set to 1. This defaults to 0. Currently this - setting only impacts prime count lower and upper - bounds, but could later be applied to other areas such - as primality testing. A later version may also have a - way to indicate whether no RH, RH, GRH, or ERH is to - be assumed. - - irand Takes a code ref to an irand function returning a - uniform number between 0 and 2**32-1. This will be - used for all random number generation in the module. + verbose The default setting of 0 will generate no extra output. + Setting to 1 or higher results in extra output. For + example, at setting 1 the AKS algorithm will indicate + the chosen r and s values. At setting 2 it will output + a sequence of dots indicating progress. Similarly, for + random_maurer_prime, setting 3 shows real time progress. + Factoring large numbers is another place where verbose + settings can give progress indications. + + xs Allows turning off the XS code, forcing the Pure Perl + code to be used. Set to 0 to disable XS, set to 1 to + re-enable. You probably will never want to do this. + + gmp Allows turning off the use of L<Math::Prime::Util::GMP>, + which means using Pure Perl code for big numbers. Set + to 0 to disable GMP, set to 1 to re-enable. + You probably will never want to do this. + + assume_rh Allows functions to assume the Riemann hypothesis is + true if set to 1. This defaults to 0. Currently this + setting only impacts prime count lower and upper + bounds, but could later be applied to other areas such + as primality testing. A later version may also have a + way to indicate whether no RH, RH, GRH, or ERH is to + be assumed. + + irand Takes a code ref to an irand function returning a + uniform number between 0 and 2**32-1. This will be + used for all random number generation in the module. =head1 FACTORING FUNCTIONS @@ -2418,21 +2437,18 @@ C<PrimeOmega[n]> function. This is same result that we would get if we evaluated the resulting array in scalar context. -The current algorithm for non-bigints is a sequence of small trial division, -a few rounds of Pollard's Rho, SQUFOF, Pollard's p-1, Hart's OLF, a long -run of Pollard's Rho, and finally trial division if anything survives. This -process is repeated for each non-prime factor. In practice, it is very rare -to require more than the first Rho + SQUFOF to find a factor, and I have not -seen anything go to the last step. +The current algorithm does a little trial division, a check for perfect +powers, followed by combinations of Pollard's Rho, SQUFOF, and Pollard's +p-1. The combination is applied to each non-prime factor found. Factoring bigints works with pure Perl, and can be very handy on 32-bit machines for numbers just over the 32-bit limit, but it can be B<very> slow -for "hard" numbers. Installing the L<Math::Prime::Util::GMP> module will speed -up bigint factoring a B<lot>, and all future effort on large number factoring -will be in that module. If you do not have that module for some reason, use -the GMP or Pari version of bigint if possible -(e.g. C<use bigint try =E<gt> 'GMP,Pari'>), which will run 2-3x faster (though -still 100x slower than the real GMP code). +for "hard" numbers. Installing the L<Math::Prime::Util::GMP> module will +speed up bigint factoring a B<lot>, and all future effort on large number +factoring will be in that module. If you do not have that module for +some reason, use the GMP or Pari version of bigint if possible +(e.g. C<use bigint try =E<gt> 'GMP,Pari'>), which will run 2-3x faster +(though still 100x slower than the real GMP code). =head2 factor_exp @@ -2460,8 +2476,6 @@ Just the way the factors are arranged is different. =head2 divisors -=head2 all_factors - my @divisors = divisors(30); # returns (1, 2, 3, 5, 6, 10, 15, 30) Produces all the divisors of a positive number input, including 1 and @@ -2483,9 +2497,10 @@ C<all_factors> is the deprecated name for this function. my @factors = trial_factor($n); -Produces the prime factors of a positive number input. The factors will be -in numerical order. +Produces the prime factors of a positive number input. +The factors will be in numerical order. For large inputs this will be very slow. +Not exported. =head2 fermat_factor @@ -2506,7 +2521,7 @@ optional number of rounds can be given as a second parameter. It is possible the function will be unable to find a factor, in which case a single element, the input, is returned. This uses Hart's One Line Factorization with no premultiplier. It is an interesting alternative to Fermat's algorithm, -and there are some inputs it can rapidly factor. In the long run it has the +and there are some inputs it can rapidly factor. Overall it has the same advantages and disadvantages as Fermat's method. =head2 squfof_factor @@ -2741,11 +2756,10 @@ Project Euler, problem 10 (summation of primes): Project Euler, problem 21 (Amicable numbers): use Math::Prime::Util qw/divisor_sum/; - sub dsum { my $n = shift; divisor_sum($n) - $n; } my $sum = 0; - foreach my $a (1..10000) { - my $b = dsum($a); - $sum += $a + $b if $b > $a && dsum($b) == $a; + foreach my $x (1..10000) { + my $y = divisor_sum($x)-$x; + $sum += $x + $y if $y > $x && $x == divisor_sum($y)-$y; } say $sum; @@ -2764,12 +2778,12 @@ Project Euler, problem 47 (Distinct primes factors): Project Euler, problem 69, stupid brute force solution (about 1 second): use Math::Prime::Util qw/euler_phi/; - my ($n, $max) = (0,0); - do { - my $ndivphi = $_ / euler_phi($_); - ($n, $max) = ($_, $ndivphi) if $ndivphi > $max; - } for 1..1000000; - say "$n $max"; + my ($maxn, $maxratio) = (0,0); + foreach my $n (1..1000000) { + my $ndivphi = $n / euler_phi($n); + ($maxn, $maxratio) = ($n, $ndivphi) if $ndivphi > $maxratio; + } + say "$maxn $maxratio"; Here is the right way to do PE problem 69 (under 0.03s): @@ -2880,13 +2894,14 @@ the first C<k> prime bases, but not much. See, for example, Nicely's L<mpz_probab_prime_p pseudoprimes|http://www.trnicely.net/misc/mpzspsp.html> page. -=item L<Math::Pari> +=item L<Math::Pari> (not recent Pari/GP) Pari 2.1.7 is the default version installed with the L<Math::Pari> module. It uses 10 random M-R bases (the PRNG uses a fixed seed set at compile time). Pari 2.3.0 was released in May 2006 and it, like all later releases through at least 2.6.1, use BPSW / APRCL, -after complaints of false results from using M-R tests. +after complaints of false results from using M-R tests. For example, +it will indicate 9 is prime about 1 out of every 276k calls. =back @@ -2930,7 +2945,7 @@ Perl threads. This section describes other CPAN modules available that have some feature overlap with this one. Also see the L</REFERENCES> section. Please let me know if any of this information is inaccurate. Also note that just because -a module doesn't match what I believe are the best set of features, doesn't +a module doesn't match what I believe are the best set of features doesn't mean it isn't perfect for someone else. I will use SoE to indicate the Sieve of Eratosthenes, and MPU to denote this @@ -2963,7 +2978,7 @@ MPXS's prime sieve is an unoptimized non-segmented SoE which returns an array. Sieve bases larger than C<10^7> start taking inordinately long and using a lot of memory (gigabytes beyond C<10^10>). E.g. C<primes(10**9, 10**9+1000)> takes 36 seconds with MPXS, but only -0.00015 seconds with MPU. +0.0001 seconds with MPU. L<Math::Prime::FastSieve> supports C<primes>, C<is_prime>, C<next_prime>, C<prev_prime>, C<prime_count>, and C<nth_prime>. The caveat is that all @@ -2981,7 +2996,7 @@ the XS sieves, and has the most memory use. It is faster than pure Perl code. L<Crypt::Primes> supports C<random_maurer_prime> functionality. MPU has more options for random primes (n-digit, n-bit, ranged, and strong) in addition to Maurer's algorithm. MPU does not have the critical bug -L<RT81858|https://rt.cpan.org/Ticket/Display.html?id=81858>. MPU should have +L<RT81858|https://rt.cpan.org/Ticket/Display.html?id=81858>. MPU has a more uniform distribution as well as return a larger subset of primes (L<RT81871|https://rt.cpan.org/Ticket/Display.html?id=81871>). MPU does not depend on L<Math::Pari> though can run slow for bigints unless @@ -2996,9 +3011,9 @@ What Crypt::Primes has that MPU does not is the ability to return a generator. L<Math::Factor::XS> calculates prime factors and factors, which correspond to the L</factor> and L</divisors> functions of MPU. These functions do not support bigints. Both are implemented with trial division, meaning they -are very fast for really small values, but quickly become unusably slow -(factoring 19 digit semiprimes is over 700 times slower). The function -C<count_prime_factors> can be done in MPU using C<scalar factor($n)>. +are very fast for really small values, but become very slow as the input +gets larger (factoring 19 digit semiprimes is over 1000 times slower). The +function C<count_prime_factors> can be done in MPU using C<scalar factor($n)>. See the L</"EXAMPLES"> section for a 2-line function replicating C<matches>. L<Math::Big> version 1.12 includes C<primes> functionality. The current @@ -3066,8 +3081,11 @@ Some of the highlights: The default L<Math::Pari> is built with Pari 2.1.7. This uses 10 M-R tests with randomly chosen bases (fixed seed, but doesn't reset each invocation like GMP's C<is_probab_prime>). This has a greater chance -of false positives compared to the BPSW test. Calling with -C<isprime($n,1)> will perform a Pocklington-Lehmer C<n-1> proof, +of false positives compared to the BPSW test -- some composites such as +C<9>, C<88831>, C<38503>, etc. +(L<OEIS A141768|http://oeis.org/A141768>) +have a surprisingly high chance of being indicated prime. +Using C<isprime($n,1)> will perform a Pocklington-Lehmer C<n-1> proof, but this becomes unreasonably slow past 70 or so digits. If L<Math::Pari> is built using Pari 2.3.5 (this requires manual @@ -3138,14 +3156,14 @@ more efficient. Without L<Math::Prime::Util::GMP> installed, MPU is very slow with bigints. With it installed, it is about 2x slower than Math::Pari. -=item C<gcd>, C<lcm>, C<kronecker>, C<znorder>, C<znprimroot> +=item C<gcd>, C<lcm>, C<kronecker>, C<znorder>, C<znprimroot>, C<znlog> Similar to MPU's L</gcd>, L</lcm>, L</kronecker>, L</znorder>, -and L</znprimroot>. Pari's C<znprimroot> only returns the smallest -root for prime powers. The behavior is undefined when the group is +L</znprimroot>, and L</znlog>. Pari's C<znprimroot> only returns the +smallest root for prime powers. The behavior is undefined when the group is not cyclic (sometimes it throws an exception, sometimes it returns -an incorrect answer). MPU's L</znprimroot> will always return the -smallest root if it exists, and C<undef> otherwise. +an incorrect answer, sometimes it hangs). MPU's L</znprimroot> will always +return the smallest root if it exists, and C<undef> otherwise. =item C<sigma> @@ -3170,10 +3188,11 @@ function supports negative and complex inputs. =back Overall, L<Math::Pari> supports a huge variety of functionality and has a -sophisticated and mature code base behind it (noting that the default version -of Pari used is about 10 years old now). -For native integers often using Math::Pari will be slower, but bigints are -often superior and it rarely has any performance surprises. Some of the +sophisticated and mature code base behind it (noting that the Pari library +used is about 10 years old now). +For native integers, typically Math::Pari will be slower than MPU. For +bigints, Math::Pari may be superior and it rarely has any performance +surprises. Some of the unique features MPU offers include super fast prime counts, nth_prime, ECPP primality proofs with certificates, approximations and limits for both, random primes, fast Mertens calculations, Chebyshev theta and psi functions, @@ -3204,7 +3223,7 @@ candidates. A test such as the BPSW test in this module is then recommended. L<Primo|http://www.ellipsa.eu/> is the best method for open source primality proving for inputs over 1000 digits. Primo also does well below that size, but other good alternatives are -L<WraithX APRCL|http://sourceforge.net/projects/mpzaprcl/>, +David Cleaver's L<mpzaprcl|http://sourceforge.net/projects/mpzaprcl/>, the APRCL from the modern L<Pari|http://pari.math.u-bordeaux.fr/> package, or the standalone ECPP from this module with large polynomial set. @@ -3337,7 +3356,7 @@ are still being tuned. L<Math::Factor::XS> is very fast when given input with only small factors, but it slows down rapidly as the smallest factor increases in size. For numbers larger than 32 bits, L<Math::Prime::Util> can be 100x or more faster (a number with only very small factors will be nearly identical, -while a semiprime with large factors will be the extreme end). L<Math::Pari> +while a semiprime may be 3000x faster). L<Math::Pari> is much slower with native sized inputs, probably due to calling overhead. For bigints, the L<Math::Prime::Util::GMP> module is needed or performance will be far worse than Math::Pari. With the GMP module, @@ -3365,7 +3384,7 @@ warrant distributed processing. =head2 PRIMALITY PROVING The C<n-1> proving algorithm in L<Math::Prime::Util::GMP> compares well to -the version including in Pari. Both are pretty fast to about 60 digits, and +the version included in Pari. Both are pretty fast to about 60 digits, and work reasonably well to 80 or so before starting to take many minutes per number on a fast computer. Version 0.09 and newer of MPU::GMP contain an ECPP implementation that, while not state of the art compared to closed source @@ -3465,51 +3484,51 @@ thank Kim Walisch for the many discussions about prime counting. =item * -Henri Cohen, "A Course in Computational Algebraic Number Theory", Springer, 1996. Practical computational number theory from the team lead of L<Pari|http://pari.math.u-bordeaux.fr/>. Lots of explicit algorithms. +Christian Bau, "The Extended Meissel-Lehmer Algorithm", 2003, preprint with example C++ implementation. Very detailed implementation-specific paper which was used for the implementation here. Highly recommended for implementing a sieve-based LMO. L<http://cs.swan.ac.uk/~csoliver/ok-sat-library/OKplatform/ExternalSources/sources/NumberTheory/ChristianBau/> =item * -Hans Riesel, "Prime Numbers and Computer Methods for Factorization", Birkh?user, 2nd edition, 1994. Lots of information, some code, easy to follow. +Manuel Benito and Juan L. Varona, "Recursive formulas related to the summation of the Möbius function", I<The Open Mathematics Journal>, v1, pp 25-34, 2007. Among many other things, shows a simple formula for computing the Mertens functions with only n/3 Möbius values (not as fast as Deléglise and Rivat, but really simple). L<http://www.unirioja.es/cu/jvarona/downloads/Benito-Varona-TOMATJ-Mertens.pdf> =item * -Pierre Dusart, "Estimates of Some Functions Over Primes without R.H.", preprint, 2010. Updates to the best non-RH bounds for prime count and nth prime. L<http://arxiv.org/abs/1002.0442/> +John Brillhart, D. H. Lehmer, and J. L. Selfridge, "New Primality Criteria and Factorizations of 2^m +/- 1", Mathematics of Computation, v29, n130, Apr 1975, pp 620-647. L<http://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf> =item * -Pierre Dusart, "Autour de la fonction qui compte le nombre de nombres premiers", PhD thesis, 1998. In French. The mathematics is readable and highly recommended reading if you're interesting in prime number bounds. L<http://www.unilim.fr/laco/theses/1998/T1998_01.html> +W. J. Cody and Henry C. Thacher, Jr., "Rational Chebyshev Approximations for the Exponential Integral E_1(x)", I<Mathematics of Computation>, v22, pp 641-649, 1968. =item * -Gabriel Mincu, "An Asymptotic Expansion", I<Journal of Inequalities in Pure and Applied Mathematics>, v4, n2, 2003. A very readable account of Cipolla's 1902 nth prime approximation. L<http://www.emis.de/journals/JIPAM/images/153_02_JIPAM/153_02.pdf> +W. J. Cody and Henry C. Thacher, Jr., "Chebyshev approximations for the exponential integral Ei(x)", I<Mathematics of Computation>, v23, pp 289-303, 1969. L<http://www.ams.org/journals/mcom/1969-23-106/S0025-5718-1969-0242349-2/> =item * -Christian Bau, "The Extended Meissel-Lehmer Algorithm", 2003, preprint with example C++ implementation. Very detailed implementation-specific paper which was used for the implementation here. Highly recommended for implementing a sieve-based LMO. L<http://cs.swan.ac.uk/~csoliver/ok-sat-library/OKplatform/ExternalSources/sources/NumberTheory/ChristianBau/> +W. J. Cody, K. E. Hillstrom, and Henry C. Thacher Jr., "Chebyshev Approximations for the Riemann Zeta Function", L<Mathematics of Computation>, v25, n115, pp 537-547, July 1971. =item * -David M. Smith, "Multiple-Precision Exponential Integral and Related Functions", I<ACM Transactions on Mathematical Software>, v37, n4, 2011. L<http://myweb.lmu.edu/dmsmith/toms2011.pdf> +Henri Cohen, "A Course in Computational Algebraic Number Theory", Springer, 1996. Practical computational number theory from the team lead of L<Pari|http://pari.math.u-bordeaux.fr/>. Lots of explicit algorithms. =item * -Vincent Pegoraro and Philipp Slusallek, "On the Evaluation of the Complex-Valued Exponential Integral", I<Journal of Graphics, GPU, and Game Tools>, v15, n3, pp 183-198, 2011. L<http://www.cs.utah.edu/~vpegorar/research/2011_JGT/paper.pdf> +Marc Deléglise and Joöl Rivat, "Computing the summation of the Möbius function", I<Experimental Mathematics>, v5, n4, pp 291-295, 1996. Enhances the Möbius computation in Lioen/van de Lune, and gives a very efficient way to compute the Mertens function. L<http://projecteuclid.org/euclid.em/1047565447> =item * -William H. Press et al., "Numerical Recipes", 3rd edition. +Pierre Dusart, "Autour de la fonction qui compte le nombre de nombres premiers", PhD thesis, 1998. In French. The mathematics is readable and highly recommended reading if you're interesting in prime number bounds. L<http://www.unilim.fr/laco/theses/1998/T1998_01.html> =item * -W. J. Cody and Henry C. Thacher, Jr., "Chebyshev approximations for the exponential integral Ei(x)", I<Mathematics of Computation>, v23, pp 289-303, 1969. L<http://www.ams.org/journals/mcom/1969-23-106/S0025-5718-1969-0242349-2/> +Pierre Dusart, "Estimates of Some Functions Over Primes without R.H.", preprint, 2010. Updates to the best non-RH bounds for prime count and nth prime. L<http://arxiv.org/abs/1002.0442/> =item * -W. J. Cody and Henry C. Thacher, Jr., "Rational Chebyshev Approximations for the Exponential Integral E_1(x)", I<Mathematics of Computation>, v22, pp 641-649, 1968. +Pierre-Alain Fouque and Mehdi Tibouchi, "Close to Uniform Prime Number Generation With Fewer Random Bits", pre-print, 2011. Describes random prime distributions, their algorithm for creating random primes using few random bits, and comparisons to other methods. Definitely worth reading for the discussions of uniformity. L<http://eprint.iacr.org/2011/481> =item * -W. J. Cody, K. E. Hillstrom, and Henry C. Thacher Jr., "Chebyshev Approximations for the Riemann Zeta Function", L<Mathematics of Computation>, v25, n115, pp 537-547, July 1971. +Walter M. Lioen and Jan van de Lune, "Systematic Computations on Mertens' Conjecture and Dirichlet's Divisor Problem by Vectorized Sieving", in I<From Universal Morphisms to Megabytes>, Centrum voor Wiskunde en Informatica, pp. 421-432, 1994. Describes a nice way to compute a range of Möbius values. L<http://walter.lioen.com/papers/LL94.pdf> =item * @@ -3517,31 +3536,31 @@ Ueli M. Maurer, "Fast Generation of Prime Numbers and Secure Public-Key Cryptogr =item * -Pierre-Alain Fouque and Mehdi Tibouchi, "Close to Uniform Prime Number Generation With Fewer Random Bits", pre-print, 2011. Describes random prime distributions, their algorithm for creating random primes using few random bits, and comparisons to other methods. Definitely worth reading for the discussions of uniformity. L<http://eprint.iacr.org/2011/481> +Gabriel Mincu, "An Asymptotic Expansion", I<Journal of Inequalities in Pure and Applied Mathematics>, v4, n2, 2003. A very readable account of Cipolla's 1902 nth prime approximation. L<http://www.emis.de/journals/JIPAM/images/153_02_JIPAM/153_02.pdf> =item * -Douglas A. Stoll and Patrick Demichel , "The impact of ζ(s) complex zeros on π(x) for x E<lt> 10^{10^{13}}", L<Mathematics of Computation>, v80, n276, pp 2381-2394, October 2011. L<http://www.ams.org/journals/mcom/2011-80-276/S0025-5718-2011-02477-4/home.html> +L<OEIS: Primorial|http://oeis.org/wiki/Primorial> =item * -L<OEIS: Primorial|http://oeis.org/wiki/Primorial> +Vincent Pegoraro and Philipp Slusallek, "On the Evaluation of the Complex-Valued Exponential Integral", I<Journal of Graphics, GPU, and Game Tools>, v15, n3, pp 183-198, 2011. L<http://www.cs.utah.edu/~vpegorar/research/2011_JGT/paper.pdf> =item * -Walter M. Lioen and Jan van de Lune, "Systematic Computations on Mertens' Conjecture and Dirichlet's Divisor Problem by Vectorized Sieving", in I<From Universal Morphisms to Megabytes>, Centrum voor Wiskunde en Informatica, pp. 421-432, 1994. Describes a nice way to compute a range of Möbius values. L<http://walter.lioen.com/papers/LL94.pdf> +William H. Press et al., "Numerical Recipes", 3rd edition. =item * -Marc Deléglise and Joöl Rivat, "Computing the summation of the Möbius function", I<Experimental Mathematics>, v5, n4, pp 291-295, 1996. Enhances the Möbius computation in Lioen/van de Lune, and gives a very efficient way to compute the Mertens function. L<http://projecteuclid.org/euclid.em/1047565447> +Hans Riesel, "Prime Numbers and Computer Methods for Factorization", Birkh?user, 2nd edition, 1994. Lots of information, some code, easy to follow. =item * -Manuel Benito and Juan L. Varona, "Recursive formulas related to the summation of the Möbius function", I<The Open Mathematics Journal>, v1, pp 25-34, 2007. Among many other things, shows a simple formula for computing the Mertens functions with only n/3 Möbius values (not as fast as Deléglise and Rivat, but really simple). L<http://www.unirioja.es/cu/jvarona/downloads/Benito-Varona-TOMATJ-Mertens.pdf> +David M. Smith, "Multiple-Precision Exponential Integral and Related Functions", I<ACM Transactions on Mathematical Software>, v37, n4, 2011. L<http://myweb.lmu.edu/dmsmith/toms2011.pdf> =item * -John Brillhart, D. H. Lehmer, and J. L. Selfridge, "New Primality Criteria and Factorizations of 2^m +/- 1", Mathematics of Computation, v29, n130, Apr 1975, pp 620-647. L<http://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf> +Douglas A. Stoll and Patrick Demichel , "The impact of ζ(s) complex zeros on π(x) for x E<lt> 10^{10^{13}}", L<Mathematics of Computation>, v80, n276, pp 2381-2394, October 2011. L<http://www.ams.org/journals/mcom/2011-80-276/S0025-5718-2011-02477-4/home.html> =back diff --git a/t/92-release-pod-coverage.t b/t/92-release-pod-coverage.t index 3d235d8..5554639 100644 --- a/t/92-release-pod-coverage.t +++ b/t/92-release-pod-coverage.t @@ -30,6 +30,8 @@ foreach my $m (@modules) { }; $param->{trustme} = [mpu_public_regex(), mpu_factor_regex()] if $m eq 'Math::Prime::Util::PP'; + $param->{trustme} = [qw/miller rabin all_factors/] + if $m eq 'Math::Prime::Util'; pod_coverage_ok( $m, $param ); } -- 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