This is currently just a personal project for playing around with number theory and cryptography constructs. My own personal intended use case is for a hobby of sometimes playing in CTFs. It re-implements some small subset of functionality from SageMath, with tweaks to API here and there according to how I see fit.
- True alpha: proof-of-concept level of code quality, API changes over night, Python will core dump on anything unexpected.
- So far it’s just basic wrapping and interaction of five “base rings,” their univariate polynomials, vectors and matrices over them.
lzz_pand related types not wrapped yet. No current plans to wrap any of the floating precision types?- Vector and matrix functionality is minimal, and will probably never be as
convenient as
numpy. - Few of the actual meaty useful number theoretic algorithms are interfaced yet.
[TODO]
from ntl.all import ZZ
# ZZ is the ring of integers and the main convenience interface.
# ZZ has some extra functionality to work directly with the number's bits:
assert ZZ(0xffff)[8::2] == 0x5500
# ZZ/n represents the quotient ring ℤ/nℤ.
F = ZZ/17
# Getting elements in this ring:
a = F(5)
print("regular arithmetic:", a**512 * (a - 1))
print("division modulo 17:", a/6)
# Polynomial rings are made with `.P` or `.Polynomial`:
Fx = F.P # Polynomials over F.
# Internally polynomials are like vectors with constant term first, lead term
# last. So [3,2,1] represents 3 + 2*x + x**2.
x = Fx([0, 1]) # Defining the polynomial `x`.
P = (x**2 + 2) * (x - 1)
Q = (x**7 - 1) * (x**2 - 1)
print(P.gcd(Q)) # Polynomial GCD.
# Polynomial slicing works, but not quite like integer bits.
assert P[1:3] == P[1] + P[2] * x
# A specialization exist for polynomials over GF2. They are accessed through
# `GF2.P`. Polynomials and extensions over GF2 also have a lot of convenience
# functionality for treating them as "vectors of bits representing integers"
# because in cryptography that's usually how they're used practically.
p = GF2.P(0xb) # 1 + x**2 + x**3
assert p + 0xb == 0
# Basic matrices and vector support also works, although a lot of convenience
# is lacking. They are accessed through `.M` or `.V`.
Fm = (ZZ/5).M
I = Fm.identity(3)
A = Fm([ [1,0,0], [2,1,0], [1,1,3] ])
assert A**20 == I
assert A[2,2] == 3
assert A[:2,:2]**5 == (ZZ/5).identity(2)Actually, you’re right! If you need anything in this library, you are probably better off using Sage instead.
There’s simply no comparison. Sage also embeds the FLINT library, which I believe is somewhat leaner for small word-sized moduli.
Also, Sage isn’t merely a kitchensink of libraries, it has several special advantages that cannot be replicated in regular CPython by adding extension types or bindings, because it builds its own version of CPython.
For example, in Sage the default type for integer literals is a wrapper for GMP, which can be a big deal depending on how much bigint arithmetic you do. GMP is a lot more efficient than Python’s simpler homemade implementation.
I would love to be able to do something like that in CPython, but I know of no way to it sanely. (There are some insane ways.) I really wish there was a way to hook into the tokenizer or parser in the Python language, e.g. by way of AST or syntax-macros, but that’s something that will probably never be added to Python.
The motivation for this library is just that I think (regular) Python ought to have basic number theoretic integer functionality, without having to resort to a gigasystem like SageMath.
This is largely missing, because for now I’m just prototyping and concentrating on actually making the basics work. I’m still not sure how I want the extension library backend to look.
There’s been some effort made to make the C-extension types as lightweight as possible (more lightweight than Sage’s, but Sage wins anyway since it compiles its own CPython), but I’m not sure this is the right approach.