io.github.daedalus/mcp-number-theory
MCP server exposing number theory functions and factorization algorithms
Versions
0.1.0latestTools 88
is_primitive_root Check if g is a primitive root modulo p.
gcd Compute the greatest common divisor of a and b.
isqrt Compute the integer square root of n.
introot Compute the integer r-th root of n. Returns None if not a perfect r-th power.
invmod Compute the modular inverse of a modulo m.
gcdext Compute the extended GCD of a and b. Returns a dict with g, x, y where g = gcd(a,b) and ax + by = g. Args: a: First integer b: Second integer Returns: Dict with keys 'g' (gcd), 'x', 'y' satisfying ax + by = g Example: >>> gcdext(48, 18) {'g': 6, 'x': -1, 'y': 3}
is_square Check if n is a perfect square.
is_cube Check if n is a perfect cube.
next_prime Find the next prime after n.
is_prime Test if n is prime using probabilistic methods.
fib Compute the n-th Fibonacci number.
primes Return a list of the first n primes.
lcm Compute the least common multiple of x and y.
invert Compute the modular inverse of a modulo b using Fermat's little theorem.
powmod Compute b^e mod m using modular exponentiation.
ilog2 Compute the integer log base 2 of n.
ilog Compute the integer log of n (natural log).
ilog10 Compute the integer log base 10 of n.
phi Compute Euler's totient function phi(n) given the prime factors of n.
chinese_remainder Solve the Chinese Remainder Theorem. Given moduli m and remainders a, find x such that x ≡ a[i] (mod m[i]). The moduli must be pairwise coprime. Args: m: List of moduli (pairwise coprime) a: List of remainders Returns: The smallest non-negative solution x Example: >>> chinese_remainder([3, 5], [2, 3]) 8 # Since 8 ≡ 2 (mod 3) and 8 ≡ 3 (mod 5)
legendre Compute the Legendre symbol (a/p).
tonelli Compute the modular square root using Tonelli-Shanks algorithm. Returns x such that x^2 ≡ n (mod p).
p_adic_valuation Return the exponent of the highest power of p dividing n.
hensel_lift_square Lift quadratic residue from mod p to mod p^k using Hensel's method.
hensel_lift_quadratic Lift root of ax^2 + bx + c ≡ 0 from mod p to mod p^k.
lucas_lehmer Test if 2^p - 1 is a Mersenne prime using Lucas-Lehmer test.
hensel_lift_cubic Lift root of ax^3 + bx^2 + cx + d ≡ 0 from mod p to mod p^k.
dlp_bruteforce Solve discrete logarithm by brute force: find x such that g^x ≡ h (mod p).
fac Compute the factorial of n.
lucas Compute the n-th Lucas number.
is_lucas Check if n is a Lucas number.
find_period Find the period of n in binary representation.
trivial_factorization_with_n_phi Factor n given phi(n). Returns (p, q) if found, None otherwise.
brent Factor n using Brent's algorithm (Pollard rho with optimizations). Returns a factor.
carmichael Factor n using Carmichael's method. Returns list of factor pairs.
fermat Factor n using Fermat's factorization method. Returns (p, q).
pollard_rho Factor n using Pollard's rho algorithm. Returns a factor.
pollard_P_1 Factor n using Pollard's P-1 algorithm. Returns (p, q) if found.
williams_pp1 Factor n using Williams' P+1 algorithm. Returns (p, q) if found.
shor Factor n using Shor's algorithm (classical part). Returns (p, q) if found.
SQUFOF Factor n using Shanks' Square Forms Factorization. Returns (p, q) if found.
hart Factor n using Hart's one-line factorization. Returns (p, q).
kraitchik Factor n using Kraitchik factorization. Returns (p, q).
lehman Factor n using Lehman's factorization algorithm. Returns (p, q) if found.
euler_factorization Factor n using Euler's factorization method. Returns (p, q) if found.
dixon Factor n using Dixon's factorization method. Returns (p, q) if found.
wiener Attack RSA using Wiener's method given modulus n and public exponent e. Returns (p, q) if vulnerable.
pollard_strassen Factor n using Pollard-Strassen algorithm. Returns (p, q) if found.
factor_XYXZ Factor integer of form x^y * x^z. Returns (p, q) if found.
factor_2PN Factor n where one factor is the prime P (p_val). Finds factors (p, q) such that n = p * q where p = p_val. Only works when n has p_val as one of its prime factors. Args: n: The integer to factor p_val: The prime factor to look for (default: 3) Returns: Tuple (p, q) where p = p_val and q = n/p, or "No factorization found" Example: >>> factor_2PN(15) (3, 5) >>> factor_2PN(14) 'No factorization found'
lehmer_machine Factor n using Lehmer's machine (fermat-based). Returns (p, q).
repunit_factor Factor n using repunit properties. Returns (p, q) if found.
factor_high_and_low_bits_equal Factor when high and low bits are equal. Returns (p, q) if found.
difference_of_powers_factor Factor using difference of powers method. Returns list of factors.
getpubkeysz Get public key size in bits.
neg_pow Calculate a^b mod n when b is negative.
contfrac_to_rational Convert continued fraction to rational number.
powmod_base_list Compute powmod for a list of bases.
powmod_exp_list Compute powmod for a list of exponents.
close_factor Factor n using close factor algorithm. Returns (p, q) if found.
inverseinversesqrt2exp Compute modular inverse square root approximation with k bits.
jacobi Compute Jacobi symbol (a/n). Returns -1, 0, or 1.
mobius Compute Möbius function. Returns 0 if n has squared prime factor.
is_square_free Check if n is square-free.
carmichael_lambda Compute Carmichael function (exponent of multiplicative group mod n).
prime_factors Return list of distinct prime factors of n.
divisors Return all positive divisors of n in ascending order.
num_divisors Count number of positive divisors of n (tau function).
sum_divisors Compute sum of all positive divisors of n (sigma function).
aliquot_sum Compute sum of proper divisors (excluding n).
is_sophie_germain Check if p is a Sophie Germain prime (p and 2p+1 are both prime).
is_safe_prime Check if p is a safe prime (p = 2q + 1 where q is prime).
prime_counting Count primes <= x.
nth_prime Return the nth prime (1-indexed).
is_prime_power Check if n = p^k for some prime p. Returns (p, k) if true.
multiplicative_order Find multiplicative order of a modulo n.
discrete_log Solve g^x ≡ h (mod p) using baby-step giant-step.
kronecker_symbol Compute Kronecker symbol (a/n).
best_rational_approximation Find best rational approximation to x with denominator <= max_denom.
primitive_root Find a primitive root modulo p. Returns None if p is not prime.
solve_linear_diophantine Solve ax + by = c for integers x, y. Returns (x, y) or None if no solution.
sum_of_two_squares Return (a, b) such that n = a^2 + b^2, or None if not representable.
partition_function Compute partition function p(n) - number of ways to write n as sum of positive integers.
is_smooth Check if n is B-smooth (all prime factors <= bound).
aks_primality Deterministic primality test using AKS algorithm.
solve_pell Solve x^2 - D*y^2 = 1, returning fundamental solution (x, y).
frobenius_number Compute Frobenius number for coprime coin denominations a, b.
integer_relation Find integer relation between real numbers using PSLQ algorithm.
Permissions 0
No permissions indexed yet.