numthy 0.2.0

Computational number theory. Pure Python. Zero dependencies. Unreasonably fast.

Computational number theory. Pure Python. Zero dependencies. Unreasonably fast.

Installation

pip install numthy

Or just drop numthy.py into your project.

Quick Start

import numthy as nt

# Primality
nt.is_prime(2**89 - 1)  # True

# Factorization (SIQS handles 50+ digits)
nt.prime_factors(2**128 + 1)  # (59649589127497217, 5704689200685129054721)

# Prime counting
nt.count_primes(10**9)  # 50847534

# Discrete log
nt.discrete_log(1000, 3, 65537)  # 50921 (i.e., 1000 ≡ 3^50921 mod 65537)

# Diophantine equations
# Solve 2x² + 3xy - 3y² + 7x - 10y - 24 = 0
solutions = nt.conic(2, 3, -3, 7, -10, -24)
next(solutions)  # (8, 10)
next(solutions)  # (376, -174)
next(solutions)  # (17304, 25218)

Demo

Try NumThy in the browser: ini.github.io/numthy/demo

Documentation

See API.md for the full reference.

Under The Hood

One file, with everything implemented from scratch. Simple API, with heavy-duty algorithms under the hood:

• Extra-strong variant of the Baillie-PSW primality test
• Lagarias-Miller-Odlyzko (LMO) algorithm for prime counting, generalized to sums over primes of any arbitrary completely multiplicative function
• Two-stage Lenstra's ECM factorization with Montgomery curves and Suyama parametrization
• Self-initializing quadratic sieve (SIQS) with triple-large-prime variation
• Cantor-Zassenhaus → Hensel lifting → Chinese Remainder Theorem pipeline for finding modular roots of polynomials
• Adleman-Manders-Miller algorithm for general n-th roots over finite fields
• General solver for all binary quadratic Diophantine equations (ax² + bxy + cy² + dx + ey + f = 0)
• Lenstra–Lenstra–Lovász lattice basis reduction algorithm with automatic precision escalation
• Jochemsz-May generalization of Coppersmith's method for multivariate polynomials with any number of variables

Requirements

Python 3.10+

That's it.

License

MIT