Revision history for Perl module Math::Prime::Util::GMP
0.21 2014-06-19
- Used a bare 64-bit in a test. Wrap in quotes.
0.20 2014-06-18
[ADDED]
- valuation(a,b) how many times does b divide a?
- invmod(a,n) inverse of a modulo n
- is_pseudoprime(n,base) Simple Fermat test
- binomial(n,k) binomial coefficient
- gcdext(a,b) extended Euclidian algorithm
- vecsum(...) sum list of integers
[OTHER]
- 10%-ish speedup for next/prev prime with 38-950 digit inputs.
0.19 2014-04-21
[ADDED]
- is_power
- exp_mangoldt
[FIXES]
- Fixed string shortcut for simple divisibility. is_prime and related
functions are a bit faster when given inputs divisible by 2 or 5.
[OTHER]
- Add improved AKS parameter selection. About 200x faster, though still
thousands of times slower than APR-CL or ECPP. Updated times for the
example in the v0.10 entry: Timing for 10**100+267:
AKS: ~5 days.
BLS75 n-1: ~3 minutes.
APR-CL: 0.09 seconds
ECPP: 0.05 seconds.
- ECPP performance adjustments, version 1.03 of standalone ECPP.
- Updated ECPP class polynomial data. Default "tiny" table had very minor
changes. The "big" table (in the github xt/ directory, default for
standalone ECPP) removed some large coefficient 17-24 degree polys to
make room for many more higher-degree polys. For some ranges this may
mean more backtracking, but should expand the input size that is able to
find good discriminants without high factoring effort. "prob" below is
summing the estimate 1/2H: 9x more polys and 66x larger size gives on
average about 3x more candidates.
Default "tiny" table:
OLD: 30373 bytes 604 polys 24 maxdeg 42.0 prob 1450 prob/MB
NEW: 30422 bytes 611 polys 25 maxdeg 42.8 prob 1475 prob/MB
"big" table at www.probableprime.org/ecpp/cpd/big/class_poly_data.h.gz
OLD: 2032376 bytes 3197 polys 117 maxdeg 104.5 prob 54 prob/MB
NEW: 2005072 bytes 5271 polys 85 maxdeg 125.2 prob 65 prob/MB
"huge" table at www.probableprime.org/ecpp/cpd/huge/class_poly_data.h.gz
15724395 bytes 14571 polys 128 maxdeg 207.9 prob 14 prob/MB
0.18 2014-01-27
[FIXES]
- Fix for 5.6.2 (undefined symbol).
- Fix for unsigned long != UV, reported by CHORNY.
0.17 2014-01-24
[ADDED]
- is_bpsw_prime specific BPSW-only test
- gcd 20-50x faster than Math::BigInt
- lcm 3-800x faster than Math::BigInt
- kronecker
[FIXES]
- Factoring with a number or intermediate near the word boundary would
hang or run very slow. Thanks to Hugo van der Sanden for the report.
- Next version of vcert.c, which handles some new Primo changes.
0.16 2013-10-28
[ADDED]
- partitions partition function p(n), OEIS A000041
[FIXES]
- Fixed memory leak in Lucas sequence (is_prime, next_prime, etc.).
- is_aks_prime wasn't properly checking divisibility for composites.
[Scripts and Programs Added]
- verify_primegap.pl parallel prime gap verification
0.15 2013-09-30
[Functions Added]
- miller_rabin_random
- A tree sieve is done in trial factor for large (900+ digits) inputs.
This improves performance greatly for very large inputs.
- is_prob_prime uses more trial division for large inputs. For very
large inputs (e.g. 50,000+ digits) this can greatly speed up probable
prime testing, for instance in next_prime or similar sieving.
Time for next_prime(99992 * 10**10101 - 100):
1m 4s MPUGMP 0.15
3m 34s Pari/GP (needs 450MB of stack!)
4m 1s mpz_nextprime
9m 33s Math::Primality
- Use shallow product tree for primorials. Large primorials are 2 to 12
times faster. Break consecutive_integer_lcm into four sub-products so
it runs 2-4x faster for large inputs.
- Trim ECPP and adjust its heuristics.
- Standalone ECPP now has consistent return codes, making it easier to
use in applications without having to parse return text. The return
codes are consistent with the certificate verifier.
- factor() in scalar context is now consistent.
0.14 2013-08-07
- Fix small certificates leaving out the "N " for small numbers.
0.13 2013-08-06
[API Changes]
- Primality proofs now use a text certificate. This is nicer for
external interaction, but is a change from previous behavior. You
will need to use Math::Prime::Util 0.30 or newer.
[Functions Added]
- lucas_sequence
- is_almost_extra_strong_lucas_pseudoprime
- is_frobenius_underwood_pseudoprime
- pplus1_factor
[Enhancements]
- is_prob_prime now uses the extra-strong Lucas test instead of the
strong Lucas test. This gives better performance. is_prime and
is_provable_prime also incorporate the change.
- Added more trial division to is_prob_prime for big (100+ digit)
numbers. This is a significant speedup for next_prime in many cases.
Pari/gp 2.6.0 nextprime(10^4000) 19 minutes
MPU:GMP 0.12 next_prime(10**4000) 15 minutes
MPU:GMP 0.13 next_prime(10**4000) 8 minutes
- ECPP now tries partial n-1 and n+1 proofs (BLS theorem 3 / 15) at each
step, and adds a couple additional quick factoring tests. This mainly
helps lower the time variability with large inputs.
- Updated ECPP polynomials. Should give better performance with larger
inputs.
[Scripts and Programs Added]
- convert-primo-cert.pl convert a Primo certificate to MPU format.
- verify-cert.pl Verify a Primo or MPU certificate.
- vcert.c Verify a Primo or MPU certificate.
0.12 2013-06-12
- add standard and extra strong Lucas probable prime tests.
- Rearrange C code to allow standalone build of ECPP.
- Speedups for ECPP.
0.11 2013-05-20
- is_prob_prime is faster at finding composites.
- rewrote Lucas inner loop for ~20% speedup.
- The previous two changes make is_prob_prime a bit faster, which means
a small speedup to almost all functions.
- Lower is_prime proving effort. Proves ~30% of 128-bit primes instead
of 50%, but runs about 4x faster.
- Change ECPP to factor all strategy with backtracking. Not much
difference below 200 digits, but a big help after that. Certificates
are identical.
0.10 2013-05-07
- ECPP -- a much faster primality prover. BLS75 n-1 works well to about
40 digits, then slows down rapidly. This ECPP implementation is good
to 300-500 digits. Timing for 10**100+267:
AKS: ~1 year. BLS75 n-1: 1.5-5 minutes. ECPP: 0.1 seconds.
- is_prime does an additional 4 random-base M-R tests.
- is_provable_prime will try a quick n-1 then do ECPP.
- is_nminus1_prime added to give access to that specific method, in
case someone has reason to insist on that proof type.
- Change polynomial multiplication to use binary segmentation. Huge
speed improvement for AKS primality proving (20-100x faster). AKS
is now faster in GMP than MPU's C code. It's still not nearly as fast
as other methods: proving 100000000003 takes 65 seconds, while this
would take a couple milliseconds at most for an n-1 proof. The one year
estimate in the first paragraph is with the _new_ code.
- Compile-time support to BLS75 theorem 7, which reduces the amount of
n-1 we need to factor. Not enabling because it just doesn't help
enough, and ECPP is a better place to spend development effort.
- Lots of new internal functions to support ECPP, which could be used
for future projects.
0.09 2013-04-21
- Add primality certificate generation.
0.08 2013-04-05
- Switch to a projective ECM with a stage 2. Much better results, but
note that it doesn't build up to B1 like the old version. This has
a big impact on factoring and primality proving.
- Add a QS based on William Hart's SIMPQS (a simple QS that is a
predecessor to what went into FLINT). Not the fastest by a long shot
(yafu and msieve take that prize), but it's quite small and works pretty
well. Eventually this will get replaced with a home-built QS. Meanwhile
some improvements from version 2.0 that remain are (1) no partial
relations, (2) uses too much memory, and (3) uses GE instead of
jasonp's block Lanczos.
- The new ECM and QS make factoring much faster, especially for 30+
digit inputs. Factoring should give reasonable times out to 70+
digits now. Time is competitive with Math::Pari now, and often faster
(noting that Math::Pari uses a fairly old version of Pari).
- Factoring mix redone given the big changes in ECM and QS.
- Primality proofs adjusted to better use p-1 and ECM. The quick proof
in is_prime has a higher success rate for all input sizes and is a
little faster for small numbers. is_provable_prime is 10-50x faster.
0.07 2013-03-19
- Tiny speedup when passing in bigints.
- Some speedups in pbrent, pbrent usage, and small prime iterator.
Factoring small (< ~30 digit) numbers is faster.
- Handle large and small M-R bases just like MPU does -- mod with n,
then return 1 if base <= 1 or base >= n-1.
0.06 2012-12-17
- Fix 1-byte memory overrun (thanks to CPAN Testers, Solaris, Valgrind).
- Add factoring of small numbers. Helps a little when the input gets
reduced enough to fit into a UV.
0.05 2012-12-15
- Add AKS primality test. Super slow, but nice to have around.
- ECM is faster.
- Add a small prime iterator, which means _much_ less memory and faster
operation for big smoothness factors in pminus1 and ecm factoring.
0.04 2012-11-11
- Add simple prime_count function. It uses next_prime so is terribly slow
for big ranges. However it's a lot faster than the PP code when given
a large base and small range e.g. (10**96, 10**96 + 2**18).
- Add primorial, pn_primorial, and consecutive_integer_lcm functions.
- Factoring:
Add a perfect power test.
Add a simple ECM factoring method.
Speed up SQUFOF a bit.
Complete p-1 rewrite. Much faster and finds more factors.
Adjust general factor() mix.
- Add Pocklington-Lehmer and BLS primality tests. is_prime() uses the
BLS test with a quick factoring attempt for numbers less than 2^200,
though the chances of success drop off as the size increases.
The point is not to cull mismarked probable primes (we use BPSW so this
is highly unlikely for these small sizes), but to quickly mark more
numbers as definitely prime. Remember to use is_prob_prime if you do
not care about this distinction and want the result slightly faster.
- add is_provable_prime function that calls BLS with much more aggressive
factoring.
0.03 2012-07-16
- XS callable: _lcm_of_consecutive_integers(B)
which is a better alternative for B! for many factoring algorithms.
- Fix some minor compile issues.
0.02 2012-07-15
- Factoring tests assumed 64-bit. Rewrite.
0.01 2012-07-15
- Initial release