• Stars
    star
    237
  • Rank 169,885 (Top 4 %)
  • Language
    Python
  • Created about 13 years ago
  • Updated over 2 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Working with numbers (primes, modular, etc.)

libnum

This is a python library for some numbers functions:

  • working with primes (generating, primality tests)
  • common maths (gcd, lcm, n'th root)
  • modular arithmetics (inverse, Jacobi symbol, square root, solve CRT)
  • converting strings to numbers or binary strings

Library may be used for learning/experimenting/research purposes. Should NOT be used for secure crypto implementations.

Installation

$ pip install libnum

Note that only Python 3 version is maintained.

Development

For development or building this repository, poetry is needed.

Tests can be ran with

$ pytest --doctest-modules .

List of functions

Common maths

  • len_in_bits(n) - number of bits in binary representation of @n
  • randint_bits(size) - random number with a given bit size
  • extract_prime_power(a, p) - s,t such that a = p**s * t
  • nroot(x, n) - truncated n'th root of x
  • gcd(a, b, ...) - greatest common divisor of all arguments
  • lcm(a, b, ...) - least common multiplier of all arguments
  • xgcd(a, b) - Extented Euclid GCD algorithm, returns (x, y, g) : a * x + b * y = gcd(a, b) = g

Modular

  • has_invmod(a, n) - checks if a has modulo inverse
  • invmod(a, n) - modulo inverse
  • solve_crt(remainders, modules) - solve Chinese Remainder Theoreme
  • factorial_mod(n, factors) - compute factorial modulo composite number, needs factorization
  • nCk_mod(n, k, factors) - compute combinations number modulo composite number, needs factorization
  • nCk_mod_prime_power(n, k, p, e) - compute combinations number modulo prime power

Modular square roots

  • jacobi(a, b) - Jacobi symbol
  • has_sqrtmod_prime_power(a, p, k) - checks if a number has modular square root, modulus is p**k
  • sqrtmod_prime_power(a, p, k) - modular square root by p**k
  • has_sqrtmod(a, factors) - checks if a composite number has modular square root, needs factorization
  • sqrtmod(a, factors) - modular square root by a composite modulus, needs factorization

Primes

  • primes(n) - list of primes not greater than @n, slow method
  • generate_prime(size, k=25) - generates a pseudo-prime with @size bits length. @k is a number of tests.
  • generate_prime_from_string(s, size=None, k=25) - generate a pseudo-prime starting with @s in string representation

Factorization

  • is_power(n) - check if @n is p**k, k >= 2: return (p, k) or False
  • factorize(n) - factorize @n (currently with rho-Pollard method) warning: format of factorization is now dict like {p1: e1, p2: e2, ...}

ECC

  • Curve(a, b, p, g, order, cofactor, seed) - class for representing elliptic curve. Methods:
  • .is_null(p) - checks if point is null
  • .is_opposite(p1, p2) - checks if 2 points are opposite
  • .check(p) - checks if point is on the curve
  • .check_x(x) - checks if there are points with given x on the curve (and returns them if any)
  • .find_points_in_range(start, end) - list of points in range of x coordinate
  • .find_points_rand(count) - list of count random points
  • .add(p1, p2) - p1 + p2 on elliptic curve
  • .power(p, n) - nβœ•P or (P + P + ... + P) n times
  • .generate(n) - nβœ•G
  • .get_order(p, limit) - slow method, trying to determine order of p; limit is max order to try

Converting

  • s2n(s) - packed string to number
  • n2s(n) - number to packed string
  • s2b(s) - packed string to binary string
  • b2s(b) - binary string to packed string

Stuff

  • grey_code(n) - number in Grey code
  • rev_grey_code(g) - number from Grey code
  • nCk(n, k) - number of combinations
  • factorial(n) - factorial

About

Author: hellman

License: MIT License