Engineering / Mathematics — Computation and Sources
Computational Number Theory: Tools and Libraries
Software for computational number theory and algebra, what each is suited to, and how to choose.
Executive summary
Implementing the algorithms in this collection from scratch is instructive and almost never the right production choice. Mature libraries encode decades of optimisation and constant-time discipline.
The choice depends on whether the need is research computation, general-purpose arithmetic, or production cryptography, and these have different requirements.
Learning objectives
- Distinguish the categories of available software.
- Match a tool to a task.
- Understand why cryptographic code has different requirements.
01Categories
Computer algebra systems
Full environments for symbolic computation, with number theory as one component. Suited to exploration and research rather than embedding.
Arbitrary precision arithmetic libraries
Highly optimised integer and rational arithmetic, used as the foundation of other software. General purpose, not hardened against side channels.
Number theory libraries
Focused implementations of the algorithms in this collection — factorisation, primality, finite fields, lattices.
Cryptographic libraries
Production implementations with constant-time discipline, side-channel resistance and security review. The only appropriate choice for deployed cryptography.
02Matching tool to task
| Task | Category | Key requirement |
|---|---|---|
| Exploring a conjecture | Computer algebra system | Interactivity and breadth |
| Large integer arithmetic in an application | Arbitrary precision library | Raw speed |
| Factoring a specific number | Number theory library or dedicated sieve tool | Algorithm quality |
| Implementing a protocol | Cryptographic library | Constant time, reviewed, maintained |
| Teaching or learning | Any, or your own implementation | Clarity over speed |
The fourth row is the one where the choice is not really a choice. Writing production cryptography from primitives is a well-documented source of catastrophic failure, and the appropriate action is to use a reviewed library at the highest level of abstraction that meets the requirement.
03Why cryptographic code differs
A correct implementation of an algorithm in this collection is not automatically a secure one. Several requirements apply to cryptographic code and to nothing else.
- Constant time. Execution time and memory access patterns must not depend on secret values, which rules out the natural implementations of extended Euclid, of square-and-multiply, and of table lookups indexed by secrets.
- Secret zeroisation. Intermediate values must be cleared, which compilers actively try to optimise away.
- Fault resistance. Computations may be verified before their results are released, since a single induced fault during RSA-CRT decryption reveals a factor of the modulus.
- Validated inputs. Received group elements must be checked for membership in the intended subgroup, or small-subgroup attacks apply.
The durable content of this collection is the method — why the algorithms work, what their costs are, and how their parameters are chosen. Translating that into deployed code is a separate discipline with its own failure modes.
04Frequently asked questions
Should the algorithms here be implemented from scratch?
For learning, absolutely — implementing Miller-Rabin or Cantor-Zassenhaus teaches more than reading about them. For production cryptography, no. The gap between correct and secure is wide and is not visible in test results.
Why avoid table lookups indexed by secrets?
Because cache timing reveals which entries were accessed. This is the mechanism behind cache-timing attacks on table-based cipher implementations, and it is why constant-time code avoids secret-dependent memory access entirely.
How are specific tools chosen?
By checking current maintenance status, security review history and platform support at the time of use — none of which is stable enough to record on a static page. The categories above are durable; the specific recommendations are not.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — orientation page, no single source section.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Forward reference: this page extends beyond the source text and is flagged as post-source.
Author: Kevin Jogin. Last reviewed 2026-08-07.