Meeting 2015 January

Anthony edited this page Jan 11, 2015 · 2 revisions

Dana Jacobsen will give a talk on his number theory module. This is an early version of the talk for FOSDEM.

This talk describes the history, design, and implementation details of a number theory module for Perl. With implementations for most functions in C, C+GMP, and Perl this offers speed on most platforms as well as portability. Comparisons will be made with tools such as Pari/GP, SymPy, SAGE, Primo, OpenPFGW, and others.

The Perl ntheory module (aka Math::Prime::Util) offers a portable solution for many integer number theory tasks in Perl. While not offering the full feature set of robust and mature packages such as Pari/GP and SAGE, there are many areas where this package offers improvements.

With implementations in C, C+GMP, and Perl, there were a number of design choices made. We describe the choices and tradeoffs of making a package that is both portable, robust, and performant. Design choices for some algorithms (e.g. primality tests) are also discussed.

Highlights of this open source package include:

  • Fastest single threaded open source prime count and nthprime
  • Fastest 64-bit primality testing
  • Fastest bigint probable prime testing to 10k digits
  • Fastest nextprime, prev_prime
  • Fastest open source AKS primality proofs
  • Fastest open source ECPP primality proofs
  • Support for random primes and random proven primes
  • Ability to compile standalone C programs for tasks such as prime count, primality tests, primality proving, and primality certificate verification.

The random primes and primality testing/proving have been used in some new crypto modules, replacing older CPAN modules that were slower and had defects. The ECPP verifier written as part of this project is being used by FactorDB. In less than a year of use, simple Perl scripts using this module have been able to find over 47% of all current record prime gaps. Numerous defects in other open source packages have been identified during testing of this module.

Meeting Notes

If you have comments on the talk or slides, email Dana

Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.