(chibi math prime)

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.

(modular-inverse a b)

Returns the multiplicative inverse of a modulo b.

(modular-expt a e m)

Returns (remainder (expt a e) m).

(coprime? n m)

Returns true iff n and m are coprime.

(provable-prime? n)

Returns true iff n is definitely prime. May take an impossibly long time for large values.

(miller-rabin-composite? n)

Returns true if we can show n to be composite by finding an exception to the Miller Rabin lemma.

(probable-prime? 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.

(prime? n)

Returns true iff n is prime. Uses provable-prime? for small n, falling back on probable-prime? for large values.

(nth-prime i)

Returns the nth prime, with 2 being the 0th prime.

(prime-below n)

Returns the first prime less than or equal to n, or #f if there are no such primes.

(prime-above n [limit])

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.

(factor n)

Returns the factorization of n as a monotonically increasing list of primes.

(totient n)

Returns the Euler totient function, the number of positive integers less than n that are relatively prime to n.

(aliquot n)

The aliquot sum s(n), equal to the sum of proper divisors of an integer n.

(perfect? n)

Returns true iff n is a perfect number, i.e. the sum of its divisors other than itself equals itself.

(random-prime lo hi)

Returns a random prime between lo, inclusive, and hi, exclusive.

(random-prime-distinct-from lo hi p)

Variant of random-prime which ensures the result is distinct from p.

(random-coprime n)

Returns a random integer less than n relatively prime to n.