a + b:
gcd(a, b):
lcm(a, b):
A generalisation of Legendre and Jacobi Symbol
(a|b):
Complexity: O(log b) multiplications modulo m.
a^b mod m:
Compute a + ar + ar^2 + … (n terms) mod m.
Complexity: O(log n) multiplications modulo m.
a + ar + ar^2 + … (n terms) mod m:
Algorithm: 16 iterations of Miller-Rabin to bases depending on the candidate itself.
(Alpertron's web calculator is better. BPSW is implemented there)
Result:
Algorithm: a million Pollard-Brent iterations before giving up. ECM yet to be implemented.
(Alpertron's web calculator is better. ECM and SIQS are implemented there)
Result:
Complexity: O(a^1.5) additions modulo m.
p(a) mod m:
Complexity: O(a) multiplications modulo m.
a! mod m:
Complexity: O(a) multiplications modulo m.
!a mod m:
Complexity: O(b) multiplications modulo m.
a P b mod m:
Complexity: O(log a) multiplications modulo m.
F(a) mod m:
Given n independent events of probability p each, what's the probability that at least k happen.
Error should be small but no guarantees.
Result: