math

Number Theory

See more details on my blog

gcd.py

• gcd(a,b)
• xgcd(a,b): return gcd(a,b),x,y, where ax+by = gcd(a,b)

isPrime

• isPrime(n): using Miller-Rabin primalrity test.
• primeSieve

euler.py

• phi(n): euler function
• sigma(n): return the sum of all factors of n

factor.py

• factor(n): return a list of numbers that are the factorization of n

modulo_equation.py

Solving modulo equations

solver  = solve()
res = solver.solveLinear(3,6,9)

res = solver.solveHigh(1,8,3,11)

res = solver.solveGroup([(5,11,2),(3,8,5),(4,1,7)])

Permutation