pyffl

Python port of the ruffl (Ruby) library: finite-field and integer arithmetic.

• Bit arithmetic: bit_arith (msb, lsb, popcount, floor_log2, etc.), BitVector, BitMatrix (row echelon, kernel basis over GF(2)).
• Integer arithmetic: int_arith (gcd, extended gcd, lcm, totient, modular exponentiation), IntMod (integers mod n), Factorization, int_factor (trial division, totient).
• Polynomials over GF(2): F2Poly (bits as coefficients), F2PolyMod (quotient ring), f2_poly_factor (Berlekamp factorization, irreducibility, totient).
• Orders: order (multiplicative order, orbit, period, generators, primitivity for IntMod and F2PolyMod).

Install

From the project root:

pip install -e .
python -m pytest tests/ -v

Usage

from pyffl import int_arith, IntMod, int_factor
from pyffl import F2Poly, F2PolyMod, f2_poly_factor, order

# Integer arithmetic
assert int_arith.gcd(24, 60) == 12
assert int_arith.ext_gcd(24, 65) == (1, 19, -7)
a = IntMod(2, 11)
assert (a ** 10).residue == 1

# Integer factorization
finfo = int_factor.factor(72)
assert finfo.all_divisors() == [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]

# F2 polynomials (hex or int: x^4 + x + 1 = 0x13)
f = F2Poly(0x13)
assert f.degree == 4
g = f2_poly_factor.factor(f)  # irreducible
assert f2_poly_factor.irr(f)

# Multiplicative order in F2[x]/(m)
m = F2Poly(0x11b)  # AES field poly
x = F2PolyMod(F2Poly(2), m)
assert order.mod_order(x) == 255

License

See LICENSE.txt. Redistribution and use in source and binary forms, with or without modification, are permitted under the terms of the BSD-style license.