SymPy Quick Reference
=====================

INSTALLATION
  pip install sympy

BASIC USAGE
  from sympy import *

NUMBER THEORY (CTF Crypto)
  # Modular inverse
  mod_inverse(e, phi)         e^(-1) mod phi

  # GCD / Extended GCD
  gcd(a, b)
  gcdex(a, b)                Returns (x, y, g) where ax + by = g

  # Factorization
  factorint(n)                Factor integer → {prime: exp}
  isprime(n)                  Primality test
  nextprime(n)                Next prime after n
  prevprime(n)                Previous prime

  # Chinese Remainder Theorem
  crt([m1, m2], [r1, r2])    Solve x ≡ ri (mod mi)

  # Discrete logarithm
  discrete_log(n, a, b)      Find x: b^x ≡ a (mod n)

  # Euler's totient
  totient(n)                  φ(n)

  # Legendre/Jacobi symbol
  legendre_symbol(a, p)
  jacobi_symbol(a, n)

  # Square root mod p
  sqrt_mod(a, p)              √a mod p
  sqrt_mod(a, p, all_roots=True)

POLYNOMIALS
  x = Symbol('x')
  p = x**3 + 2*x + 1
  roots = solve(p, x)        Find roots
  factor(p)                   Factor polynomial

  # Polynomial over finite field
  from sympy import GF
  F = GF(p)                   Field of integers mod p

MATRICES
  M = Matrix([[1, 2], [3, 4]])
  M.det()                     Determinant
  M.inv()                     Inverse
  M * M                       Multiplication
  M.eigenvals()               Eigenvalues
  M.rref()                    Row echelon form

SOLVING EQUATIONS
  x, y = symbols('x y')
  solve(x**2 - 4, x)          → [-2, 2]
  solve([x + y - 5, x - y - 1], [x, y])

COMMON RSA PATTERNS
  # Factor n when p and q are close
  from sympy import integer_nthroot
  s = integer_nthroot(n, 2)[0]
  # Then search near s for factors

  # Recover d from (e, phi)
  d = mod_inverse(e, phi)
  m = pow(c, d, n)

  # Wiener's attack (small d)
  # Use continued fraction expansion
  from sympy import continued_fraction_iterator, Rational
  cf = list(continued_fraction_iterator(Rational(e, n)))
