Prime and number theoretic utilities.
Returns the multiplicative inverse of a modulo b.
Returns (remainder (expt a e) m).
Returns true iff n and m are coprime.
Returns true iff n is definitely prime. May take an
impossibly long time for large values.
Returns true if we can show n to be composite
using the Miller-Rabin test (i.e., finding a witness a
where a^(n-1)≠1 mod n or a reveals
the existence of a 3rd square root of 1 in Z/(n))
Returns true if n has a very high probability (enough that
you can assume a false positive will never occur in your lifetime)
of being prime.
Returns true iff n is prime. Uses provable-prime?
for small n, falling back on probable-prime? for
large values.
Returns the nth prime, with 2 being the 0th prime.
Returns the first prime less than or equal to n, or #f if
there are no such primes.
Returns the first prime greater than or equal to n. If the
optional limit is given and not false, returns #f
if no such primes exist below limit.
Returns the factorization of n as a list of
elements of the form (,
where p . k)p is a prime factor
and k is its multiplicity.
Returns the factorization of n as a monotonically
increasing list of primes.
The Euler totient φ(n) is the number of positive
integers less than or equal to n that are
relatively prime to n.
The aliquot sum s(n) is
the sum of proper divisors of a positive integer n.
Returns true iff n is a perfect number, i.e. the sum of its
divisors other than itself equals itself.
Returns a random prime between lo, inclusive, and hi,
exclusive.
Variant of random-prime which ensures the result is
distinct from p.
Returns a random integer less than n relatively prime to
n.