Prime and number theoretic utilities. Returns a pair whose car is the power of 2 in the factorization of n, and whose cdr is the product of all remaining primes.
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 by finding an
exception to the Miller Rabin lemma.
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 monotonically
increasing list of primes.
Returns the Euler totient function, the number of positive
integers less than n that are relatively prime to n.
The aliquot sum s(n), equal to the sum of proper divisors of an 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.