Software, Tables and Sources
Number Theory Software Packages
The computer algebra systems and libraries implementing these algorithms, what each is suited to, and why implementing from scratch is usually the wrong choice.
Engineering / MathematicsSoftware, Tables and Sources2 min readKV-MATH-0677
Nearly every algorithm in this collection is available in mature software. Understanding the algorithms is necessary for using those tools well; reimplementing them rarely is.
Categories of tool
| Category | Character | Suits |
|---|---|---|
| General computer algebra systems | Broad coverage, interactive, scriptable | Exploration and one-off computation |
| Number-theory-specific systems | Deep coverage of number fields and curves | Serious number theory work |
| Arithmetic libraries | Fast primitives; no high-level structures | Embedding in a larger program |
| Specialist factoring and sieving codes | One task, extremely optimised | Record computations |
What mature implementations encode
- Tuned crossover points between algorithm variants, established by measurement rather than analysis.
- Parameter tables for ECM bounds and Jacobi sum test parameters.
- Handling of the special cases — characteristic two and three, wildly ramified primes, defective sub-resultant steps.
- Extensive regression suites accumulated from real failures.
When to implement yourself
Learning
Implementing an algorithm is the most reliable way to understand it. The result need not be fast.
A genuinely novel variant
Where no existing implementation covers the case.
Tight embedding constraints
Where a library cannot be used for licensing, size or platform reasons.
Verification
An independent implementation is exactly what checking a certificate calls for.
Choosing
Choosing a package
- Identify the dominant operationClass groups, factoring, curves and polynomial arithmetic have different leaders.
- Check the scaleInteractive exploration and record computation call for different tools.
- Check verification supportWhether certificates and independent checks are available.
- Benchmark on your own inputsPublished comparisons rarely match a specific workload.
Interoperability
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — App. A. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.