tessl/pypi-gmpy2
Multiple-precision arithmetic library providing fast GMP, MPFR, and MPC interfaces for Python
—
Pending
number-theory.mddocs/
Number Theory
gmpy2 provides extensive number theory functionality including GCD/LCM operations, modular arithmetic, primality testing, integer sequences, and advanced primality tests suitable for cryptographic applications.
Capabilities
GCD and LCM Operations
Greatest Common Divisor and Least Common Multiple operations with extended algorithms.
def gcd(*args):
"""
Greatest Common Divisor of one or more integers.
Args:
*args: Integer values
Returns:
mpz: GCD of all arguments
Note:
For multiple arguments, computes GCD iteratively
"""
def gcdext(a, b):
"""
Extended Euclidean Algorithm.
Args:
a, b: Integer values
Returns:
tuple: (gcd, s, t) where gcd = s*a + t*b
Note:
Useful for computing modular inverses
"""
def lcm(*args):
"""
Least Common Multiple of one or more integers.
Args:
*args: Integer values
Returns:
mpz: LCM of all arguments
"""Modular Arithmetic
Modular inverse and division operations.
def invert(x, y):
"""
Modular inverse of x modulo y.
Args:
x: Value to invert
y: Modulus
Returns:
mpz: z such that (x * z) ≡ 1 (mod y)
Raises:
ValueError: If gcd(x, y) != 1 (no inverse exists)
"""
def divm(a, b, m):
"""
Modular division: compute (a / b) mod m.
Args:
a: Dividend
b: Divisor
m: Modulus
Returns:
mpz: Result of (a * invert(b, m)) mod m
"""Primality Testing
Comprehensive primality testing with multiple algorithms.
def is_prime(x, n=25):
"""
Miller-Rabin primality test.
Args:
x: Integer to test
n: Number of test rounds (default 25)
Returns:
bool: True if probably prime, False if composite
Note:
Probability of error is at most 4^(-n)
"""
def is_probab_prime(x, n=25):
"""
Probabilistic primality test with detailed result.
Args:
x: Integer to test
n: Number of test rounds
Returns:
int: 0 if composite, 1 if probably prime, 2 if definitely prime
"""
def next_prime(x):
"""
Find next prime number greater than x.
Args:
x: Starting value
Returns:
mpz: Next prime after x
"""
def prev_prime(x):
"""
Find previous prime number less than x (GMP 6.3.0+).
Args:
x: Starting value
Returns:
mpz: Previous prime before x
"""Advanced Primality Tests
Specialized primality tests for cryptographic and research applications.
def is_bpsw_prp(x):
"""
Baillie-PSW probable prime test.
Args:
x: Integer to test
Returns:
bool: True if passes BPSW test
Note:
Very strong test with no known counterexamples < 2^64
"""
def is_strong_bpsw_prp(x):
"""
Strong Baillie-PSW probable prime test.
Args:
x: Integer to test
Returns:
bool: True if passes strong BPSW test
"""
def is_fermat_prp(x, a):
"""
Fermat probable prime test to base a.
Args:
x: Integer to test
a: Test base
Returns:
bool: True if x passes Fermat test to base a
"""
def is_euler_prp(x, a):
"""
Euler probable prime test to base a.
Args:
x: Integer to test
a: Test base
Returns:
bool: True if x passes Euler test to base a
"""
def is_strong_prp(x, a):
"""
Strong probable prime test (Miller-Rabin) to base a.
Args:
x: Integer to test
a: Test base
Returns:
bool: True if x passes strong test to base a
"""
def is_lucas_prp(x):
"""
Lucas probable prime test.
Args:
x: Integer to test
Returns:
bool: True if x passes Lucas test
"""
def is_strong_lucas_prp(x):
"""
Strong Lucas probable prime test.
Args:
x: Integer to test
Returns:
bool: True if x passes strong Lucas test
"""
def is_extra_strong_lucas_prp(x):
"""
Extra strong Lucas probable prime test.
Args:
x: Integer to test
Returns:
bool: True if x passes extra strong Lucas test
"""
def is_selfridge_prp(x):
"""
Selfridge probable prime test.
Args:
x: Integer to test
Returns:
bool: True if x passes Selfridge test
"""
def is_strong_selfridge_prp(x):
"""
Strong Selfridge probable prime test.
Args:
x: Integer to test
Returns:
bool: True if x passes strong Selfridge test
"""
def is_fibonacci_prp(x):
"""
Fibonacci probable prime test.
Args:
x: Integer to test
Returns:
bool: True if x passes Fibonacci test
"""Legendre, Jacobi, and Kronecker Symbols
Number theory symbols for quadratic residue testing.
def legendre(a, p):
"""
Legendre symbol (a/p).
Args:
a: Integer
p: Odd prime
Returns:
int: -1, 0, or 1
Note:
Returns 1 if a is quadratic residue mod p, -1 if not, 0 if a ≡ 0 (mod p)
"""
def jacobi(a, b):
"""
Jacobi symbol (a/b).
Args:
a: Integer
b: Positive odd integer
Returns:
int: -1, 0, or 1
Note:
Generalization of Legendre symbol
"""
def kronecker(a, b):
"""
Kronecker symbol (a/b).
Args:
a: Integer
b: Integer
Returns:
int: -1, 0, or 1
Note:
Further generalization allowing even b
"""Combinatorial Functions
Factorial and binomial coefficient calculations.
def fac(n):
"""
Factorial of n.
Args:
n: Non-negative integer
Returns:
mpz: n!
"""
def double_fac(n):
"""
Double factorial of n (n!!).
Args:
n: Non-negative integer
Returns:
mpz: n!! = n * (n-2) * (n-4) * ... * 1 or 2
"""
def multi_fac(n, m):
"""
Multi-factorial of n with step m.
Args:
n: Non-negative integer
m: Step size
Returns:
mpz: n * (n-m) * (n-2m) * ...
"""
def primorial(n):
"""
Primorial of n (product of primes <= n).
Args:
n: Non-negative integer
Returns:
mpz: Product of all primes <= n
"""
def bincoef(n, k):
"""
Binomial coefficient C(n, k).
Args:
n: Integer
k: Non-negative integer
Returns:
mpz: n! / (k! * (n-k)!)
Note:
Also available as comb(n, k)
"""
def comb(n, k):
"""
Binomial coefficient C(n, k) (alias for bincoef).
Args:
n: Integer
k: Non-negative integer
Returns:
mpz: n! / (k! * (n-k)!)
"""Integer Sequences
Fibonacci, Lucas, and related sequence generators.
def fib(n):
"""
nth Fibonacci number.
Args:
n: Non-negative integer
Returns:
mpz: F(n) where F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
"""
def fib2(n):
"""
nth Fibonacci number and its predecessor.
Args:
n: Non-negative integer
Returns:
tuple: (F(n), F(n-1))
"""
def lucas(n):
"""
nth Lucas number.
Args:
n: Non-negative integer
Returns:
mpz: L(n) where L(0)=2, L(1)=1, L(n)=L(n-1)+L(n-2)
"""
def lucas2(n):
"""
nth Lucas number and its predecessor.
Args:
n: Non-negative integer
Returns:
tuple: (L(n), L(n-1))
"""
def lucasu(p, q, n):
"""
Lucas U sequence U_n(p, q).
Args:
p, q: Parameters
n: Index
Returns:
mpz: U_n(p, q)
"""
def lucasu_mod(p, q, n, m):
"""
Lucas U sequence U_n(p, q) mod m.
Args:
p, q: Parameters
n: Index
m: Modulus
Returns:
mpz: U_n(p, q) mod m
"""
def lucasv(p, q, n):
"""
Lucas V sequence V_n(p, q).
Args:
p, q: Parameters
n: Index
Returns:
mpz: V_n(p, q)
"""
def lucasv_mod(p, q, n, m):
"""
Lucas V sequence V_n(p, q) mod m.
Args:
p, q: Parameters
n: Index
m: Modulus
Returns:
mpz: V_n(p, q) mod m
"""Factor Manipulation
Functions for working with prime factors.
def remove(x, f):
"""
Remove all occurrences of factor f from x.
Args:
x: Integer to factor
f: Factor to remove
Returns:
tuple: (result, count) where result = x / f^count
Note:
Efficiently removes highest power of f that divides x
"""Integer Property Tests
Tests for various integer properties.
def is_even(x):
"""
Test if integer is even.
Args:
x: Integer value
Returns:
bool: True if x is even
"""
def is_odd(x):
"""
Test if integer is odd.
Args:
x: Integer value
Returns:
bool: True if x is odd
"""
def is_square(x):
"""
Test if integer is a perfect square.
Args:
x: Integer value
Returns:
bool: True if x = k^2 for some integer k
"""
def is_power(x):
"""
Test if integer is a perfect power.
Args:
x: Integer value
Returns:
bool: True if x = k^n for some integers k, n with n > 1
"""
def is_congruent(x, y, m):
"""
Test if x ≡ y (mod m).
Args:
x, y: Integer values
m: Modulus
Returns:
bool: True if x and y are congruent modulo m
"""
def is_divisible(x, y):
"""
Test if x is divisible by y.
Args:
x, y: Integer values
Returns:
bool: True if y divides x evenly
"""Usage Examples
Basic Number Theory
import gmpy2
# GCD and LCM
a = gmpy2.mpz(48)
b = gmpy2.mpz(18)
print(f"GCD: {gmpy2.gcd(a, b)}") # 6
print(f"LCM: {gmpy2.lcm(a, b)}") # 144
# Extended GCD
gcd, s, t = gmpy2.gcdext(a, b)
print(f"GCD: {gcd}, s: {s}, t: {t}")
print(f"Verification: {s * a + t * b}") # Should equal gcdPrimality Testing
import gmpy2
# Test various numbers for primality
candidates = [97, 98, 99, 101, 1009, 1013]
for n in candidates:
is_prime = gmpy2.is_prime(n)
prob_prime = gmpy2.is_probab_prime(n)
print(f"{n}: is_prime={is_prime}, probab_prime={prob_prime}")
# Find next prime
start = gmpy2.mpz(1000)
next_p = gmpy2.next_prime(start)
print(f"Next prime after {start}: {next_p}")Advanced Primality Testing
import gmpy2
# Large number for testing
large_num = gmpy2.mpz("1000000000000000000000000000057")
# Various primality tests
tests = [
("BPSW", gmpy2.is_bpsw_prp),
("Strong BPSW", gmpy2.is_strong_bpsw_prp),
]
for name, test_func in tests:
result = test_func(large_num)
print(f"{name} test: {result}")
# Base-specific tests
base = 2
fermat_result = gmpy2.is_fermat_prp(large_num, base)
strong_result = gmpy2.is_strong_prp(large_num, base)
print(f"Fermat base {base}: {fermat_result}")
print(f"Strong base {base}: {strong_result}")Modular Arithmetic
import gmpy2
# Modular inverse example
a = gmpy2.mpz(3)
m = gmpy2.mpz(11)
inv = gmpy2.invert(a, m)
print(f"Inverse of {a} modulo {m}: {inv}")
print(f"Verification: ({a} * {inv}) mod {m} = {(a * inv) % m}")
# Modular division
dividend = gmpy2.mpz(15)
divisor = gmpy2.mpz(7)
modulus = gmpy2.mpz(11)
result = gmpy2.divm(dividend, divisor, modulus)
print(f"({dividend} / {divisor}) mod {modulus} = {result}")Combinatorial Functions
import gmpy2
# Factorials
n = 20
print(f"{n}! = {gmpy2.fac(n)}")
print(f"{n}!! = {gmpy2.double_fac(n)}")
# Binomial coefficients
n, k = 10, 3
coeff = gmpy2.bincoef(n, k)
print(f"C({n}, {k}) = {coeff}")
# Fibonacci numbers
fib_n = gmpy2.fib(50)
fib_n, fib_n_minus_1 = gmpy2.fib2(50)
print(f"F(50) = {fib_n}")
print(f"F(49) = {fib_n_minus_1}")Integer Sequences
import gmpy2
# Generate Fibonacci sequence
print("First 10 Fibonacci numbers:")
for i in range(10):
print(f"F({i}) = {gmpy2.fib(i)}")
# Lucas numbers
print("\nFirst 10 Lucas numbers:")
for i in range(10):
print(f"L({i}) = {gmpy2.lucas(i)}")
# Custom Lucas sequences
p, q = 1, -1 # Parameters for Fibonacci-like sequence
for i in range(5):
u_val = gmpy2.lucasu(p, q, i)
v_val = gmpy2.lucasv(p, q, i)
print(f"U_{i}({p},{q}) = {u_val}, V_{i}({p},{q}) = {v_val}")Install with Tessl CLI
npx tessl i tessl/pypi-gmpy2