Skip to content

Latest commit

 

History

History
102 lines (73 loc) · 3.65 KB

README.md

File metadata and controls

102 lines (73 loc) · 3.65 KB
Raw

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