pyrival.algebra¶
pyrival.algebra.chinese_remainder¶
-
pyrival.algebra.chinese_remainder.chinese_remainder(a, p)¶ returns x s.t. x = a[i] (mod p[i]) where p[i] is prime for all i
-
pyrival.algebra.chinese_remainder.composite_crt(b, m)¶ returns x s.t. x = b[i] (mod m[i]) for all i
-
pyrival.algebra.chinese_remainder.extended_gcd(a, b)¶ returns gcd(a, b), s, r s.t. a * s + b * r == gcd(a, b)
-
pyrival.algebra.chinese_remainder.gcd(x, y)¶ greatest common divisor of x and y
pyrival.algebra.discrete_log¶
-
pyrival.algebra.discrete_log.discrete_log(a, b, mod)¶ Returns smallest x > 0 s.t. pow(a, x, mod) == b or None if no such x exists. Note: works even if a and mod are not coprime.
pyrival.algebra.factors¶
-
pyrival.algebra.factors.all_factors(n)¶ returns a sorted list of all distinct factors of n
-
pyrival.algebra.factors.distinct_factors(n)¶ returns a list of all distinct factors of n
-
pyrival.algebra.factors.gcd(x, y)¶ greatest common divisor of x and y
-
pyrival.algebra.factors.memodict(f)¶ memoization decorator for a function taking a single argument
-
pyrival.algebra.factors.pollard_rho(n)¶ returns a random factor of n
-
pyrival.algebra.factors.prime_factors()¶ x.__getitem__(y) <==> x[y]
pyrival.algebra.fft¶
-
pyrival.algebra.fft.fft(P)¶
-
pyrival.algebra.fft.fft_conv(P, Q)¶
-
pyrival.algebra.fft.ifft(P)¶
pyrival.algebra.fst¶
-
pyrival.algebra.fst.fst(a, oplus=<built-in function and_>, inv=False)¶
-
pyrival.algebra.fst.fst_conv(a, b)¶
pyrival.algebra.gcd¶
-
pyrival.algebra.gcd.extended_gcd(a, b)¶ returns gcd(a, b), s, r s.t. a * s + b * r == gcd(a, b)
-
pyrival.algebra.gcd.gcd(x, y)¶ greatest common divisor of x and y
-
pyrival.algebra.gcd.gcdm(*args)¶
-
pyrival.algebra.gcd.lcm(a, b)¶
-
pyrival.algebra.gcd.lcmm(*args)¶
pyrival.algebra.is_prime¶
-
pyrival.algebra.is_prime.is_prime(n)¶ returns True if n is prime else False
pyrival.algebra.modinv¶
-
pyrival.algebra.modinv.extended_gcd(a, b)¶ returns gcd(a, b), s, r s.t. a * s + b * r == gcd(a, b)
-
pyrival.algebra.modinv.modinv(a, m)¶ returns the modular inverse of a w.r.t. to m, works when a and m are coprime
pyrival.algebra.ntt¶
-
pyrival.algebra.ntt.intt(P)¶
-
pyrival.algebra.ntt.ntt(P)¶
-
pyrival.algebra.ntt.ntt_conv(P, Q)¶
pyrival.algebra.primitive_root¶
-
pyrival.algebra.primitive_root.gcd(x, y)¶ greatest common divisor of x and y
-
pyrival.algebra.primitive_root.ilog(n)¶ returns the smallest a, b s.t. a**b = n for integer a, b
-
pyrival.algebra.primitive_root.memodict(f)¶ memoization decorator for a function taking a single argument
-
pyrival.algebra.primitive_root.pollard_rho(n)¶ returns a random factor of n
-
pyrival.algebra.primitive_root.prime_factors()¶ x.__getitem__(y) <==> x[y]
-
pyrival.algebra.primitive_root.primitive_root(p)¶ returns a primitive root of p