Use the library; verify across two of them
The algorithms in this knowledge stream are implemented, optimised and battle-tested in existing systems. Reimplementing them is justified for learning, for embedding in a constrained environment, or for genuinely novel research — and almost never otherwise. The more valuable discipline is cross-verification: computing an invariant in two independent systems catches errors that no single system will report, because the characteristic failure here is a plausible wrong answer rather than a crash.
Learning objectives
- Select an appropriate system for a given class of computation.
- Distinguish general systems from specialised arithmetic libraries.
- Apply cross-verification as standard practice.
- Record the conditionality attached to a computed result.
Section 01The main systems
| System | Character | Particular strengths | Considerations |
|---|---|---|---|
| PARI/GP | Specialised, open source | Number fields, class groups, units, elliptic curves; exceptionally fast for its domain; usable as the C library libpari | Deliberately narrow scope; terse interface |
| SageMath | Integrating system, open source | Python interface unifying PARI, FLINT, NTL, Singular and others; excellent for exploratory work and teaching | Large installation; some operations dispatch to a backend whose conventions differ |
| Magma | Commercial | Very broad and deep algebraic coverage; often the reference implementation for advanced algorithms | Licence cost; closed source, so results cannot be independently audited |
| FLINT | C library, open source | Fast polynomial and integer arithmetic; the arithmetic engine beneath several systems | A library, not a system — no interactive layer |
| GMP | C library, open source | The reference multiprecision integer implementation; extensively hand-optimised | Arithmetic only; no number-theoretic structures |
| NTL | C++ library, open source | Lattice reduction, polynomial arithmetic over finite fields | Overlaps with FLINT; choose by benchmark for the specific workload |
For a class group, PARI/GP or Magma. For fast polynomial arithmetic inside a larger program, FLINT or NTL. For multiprecision integers alone, GMP. Using a full computer algebra system as an arithmetic library, or a bare arithmetic library for number field work, are both avoidable mismatches.
Section 02Cross-verification
The dominant failure mode in this subject is a well-formed wrong answer. Two independent systems agreeing is far stronger evidence than one system succeeding.
- Stage 01Compute in system ARecord the invariant, the exact input and any options set.
- Stage 02Compute in system BUse an independent implementation, ideally not sharing a backend — note that Sage frequently delegates to PARI, so that pair is not independent.
- Stage 03Compare invariantsClass number and structure, regulator to a stated precision, discriminant, unit rank, and the fundamental identity for prime decomposition.
- Stage 04Apply analytic checksVerify hR against the analytic class number formula, and check statistical agreement with the Cohen–Lenstra predictions across a family.
Systems differ on the sign of the discriminant in some conventions, on whether the regulator includes a factor for the unit index, on row versus column Hermite normal form, and on proper versus improper equivalence of quadratic forms. A disagreement should prompt a convention check before an error report.
Section 03Recording a result
| Field | Why |
|---|---|
| System and version | Algorithms and defaults change between releases |
| Exact input | Defining polynomial, not just the field name |
| Options and bounds | Factor base bound, precision, proof flags |
| Conditionality | Whether the result assumes GRH, and whether the discriminant was fully factored |
| Verification performed | Which independent checks were run and their outcome |
| Precision | For real quantities such as the regulator, the number of certified digits |
Several systems run class group computations under GRH by default and offer a certification option that is far slower. A result obtained with the default is conditional, and the flag setting must be recorded with it. Reporting such a value as unconditional is a factual error, not a stylistic one.
ReferenceFrequently asked questions
Should this layer ever be implemented from scratch?
For learning, yes — implementing LLL or Tonelli–Shanks teaches more than reading about them. For production, only when embedding in an environment where no library is available, or when the algorithm is genuinely new. Reimplementing a class group algorithm to use in research is a large project with a high probability of subtle error.
Are Sage and PARI independent for verification purposes?
Frequently not — Sage delegates much number field work to PARI, so agreement between them may reflect a single implementation. Genuine cross-verification requires systems with independent code paths, and checking which backend was used is part of the exercise.
How should precision be handled for real invariants?
Compute at increasing precision until successive results agree to the required number of digits, and record the certified precision alongside the value. A regulator quoted without its precision cannot be meaningfully compared with another computation.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.