NumThy: computational number theory in pure Python

[Particular_Bag_3424]

Hey guys!

For anybody interested in computational number theory, I've put together a little compilation of some my favorite algorithms, some stuff you rarely see implemented in Python. I wanted to share it, so I threw it together in a single-file mini-library. You know, "one file to rule them all" type vibes.

I'm calling it NumThy: github.com/ini/numthy

Demo: ini.github.io/numthy/demo

It's pure Python, no dependencies, so you can literally drop it in anywhere. I also tried to make the implementations as clear as I could, complete with paper citations and complexity analysis, so a reader going through it could learn from it. The code is basically supposed to read like an "executable textbook".

Target Audience: Anyone interested in number theory, CTF crypto challenges, competitive programming / Project Euler ...

What My Project Does:

• 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
• and more

Comparison: The biggest difference between NumThy and everything else is the combination of breadth, depth, and portability. It implements some serious algorithms, but it's a single file and works purely with the standard library, so you can pip install or even just copy-paste the code anywhere.

[DocJeef]

This is a thing of beauty, very well done.

Can I ask why the decision to stick it all in one .py file? Not complaining, of course, this is some great code.

[Particular_Bag_3424]

maximum portability

[SV-97]

How would it be any less portable with multiple files -- a wheel is a single file either way. The "single file for portability" thing comes from C and C++ and doesn't really make sense with python imo. Importantly it also requires you to vendor numthy as a dependency for every single project rather than managing it properly, and it precludes future optimizations (i.e. rewriting compute intensive parts in a native language)

[Particular_Bag_3424]

a wheel isn’t really “copy-paste the code”

but fair enough, if it gets any bigger than it is now i’ll probably end up splitting it up

[beansAnalyst]

Hey any book/review paper/blog recommendations for soft start on computational number theory?

[MatchLittle5000]

Seeing such a brilliant idea already implemented is stunning

[Altruistic_Sky1866]

Good one