HMath.NumberTheory¶

Description

Exact integer algorithms. Expensive searches take an explicit nonnegative iteration budget and report NonConvergence. Primality by trial division is proven; Miller--Rabin and Baillie--PSW are explicitly probable-prime tests.

On this page¶

API	Purpose
gcdInteger	Nonnegative greatest common divisor; gcdInteger 0 0 = 0.
lcmInteger	Nonnegative least common multiple; zero if either argument is zero.
extendedGCD	(g,x,y) with ax+by=g>=0, also for negative inputs and zero.
bezout	Bezout coefficients only; see extendedGCD.
modPow	Binary modular exponentiation.
modInverse	Canonical inverse residue in [0,m).
chineseRemainder	Generalized CRT for (residue,positive modulus) pairs.
linearDiophantine	One solution and a direction: (x,y,dx,dy) represents every solution (x+kdx,y+kdy) of ax+by=c.
integerSquareRoot	Floor of the square root, computed by exact integer Newton iteration.
perfectPower	Find a representation n = base^exponent with exponent greater than one.
isPrimeExact	Proven primality using trial division.
nextPrime	First proven prime at least the requested integer.
millerRabin	Strong Miller--Rabin for explicitly supplied bases (each >=2).
bailliePSW	Baillie--PSW: base-2 strong Miller--Rabin plus strong Lucas--Selfridge.
sieveEratosthenes	Eratosthenes sieve through an inclusive nonnegative upper bound.
sieveAtkin	Atkin quadratic-residue sieve, followed by removal of prime-square multiples.
segmentedSieve	Segmented sieve on the inclusive interval [lo,hi].
primeFactorization	Exact trial factorization of a positive integer.
pollardRho	Pollard rho with Floyd cycle detection, explicit seed and iteration budget.
pollardPMinusOne	Pollard p-1 stage one with a smoothness bound >=2 and base.
fermatFactor	Fermat difference-of-squares factorization, with an explicit step budget.
divisors	All positive divisors in increasing order, under a factorization budget.
divisorSum	Sum of positive divisors.
divisorCount	Number of positive divisors.
eulerTotient	Euler totient, including phi(1)=1.
carmichael	Carmichael's exponent of the multiplicative unit group.
mobius	Mobius function on positive integers.
liouville	Liouville function, counting prime factors with multiplicity.
multiplicativeOrder	Multiplicative order of a unit modulo a modulus >1.
primitiveRoot	Smallest generator of the units modulo m, if that group is cyclic.
discreteLog	Baby-step giant-step discrete logarithm of a unit.
legendreSymbol	Legendre symbol for a proven odd prime modulus, with proof budget.
jacobiSymbol	Jacobi symbol for a positive odd denominator.
kroneckerSymbol	Kronecker symbol, extending Jacobi to every integer denominator.
tonelliShanks	Tonelli--Shanks modular square root for a proven prime modulus.
continuedFraction	Finite simple continued fraction of a rational, using floor division.
fromContinuedFraction	Evaluate a finite continued fraction.
convergents	Successive convergents, rejecting invalid finite prefixes.
farey	Farey sequence of positive order, including zero and one.
pellFundamental	Minimal positive solution to x^2-d*y^2=1 via continued fractions of sqrt d.
isPerfectNumber	Perfect-number predicate on positive integers.
areAmicable	Amicable-number predicate; equal numbers are not an amicable pair.
partitions	Integer partitions in descending part order.
partitionCount	Partition count by exact dynamic programming, O(n^2) work and O(n) storage.
fibonacciFast	Signed-index Fibonacci by fast doubling; F(-n)=(-1)^(n+1)F(n).

Documentation

gcdInteger

gcdInteger :: Integer -> Integer -> Integer Source #

Nonnegative greatest common divisor; gcdInteger 0 0 = 0.

lcmInteger

lcmInteger :: Integer -> Integer -> Integer Source #

Nonnegative least common multiple; zero if either argument is zero.

extendedGCD

extendedGCD :: Integer -> Integer -> (Integer, Integer, Integer) Source #

(g,x,y) with a*x+b*y=g>=0, also for negative inputs and zero.

bezout

bezout :: Integer -> Integer -> (Integer, Integer) Source #

Bezout coefficients only; see extendedGCD.

modPow

modPow :: Integer -> Integer -> Integer -> Either MathError Integer Source #

Binary modular exponentiation. Modulus must be positive. Negative powers use a modular inverse and fail when the base is not a unit.

modInverse

modInverse :: Integer -> Integer -> Either MathError Integer Source #

Canonical inverse residue in [0,m). Modulus must exceed one.

chineseRemainder

chineseRemainder :: [(Integer, Integer)] -> Either MathError (Integer, Integer) Source #

Generalized CRT for (residue,positive modulus) pairs. Compatible noncoprime moduli are supported. Returns canonical residue and lcm modulus.

linearDiophantine

linearDiophantine :: Integer -> Integer -> Integer -> Either MathError (Integer, Integer, Integer, Integer) Source #

One solution and a direction: (x,y,dx,dy) represents every solution (x+k*dx,y+k*dy) of a*x+b*y=c. The all-zero equation has a two-dimensional solution set and is rejected instead of returning a misleading direction.

integerSquareRoot

integerSquareRoot :: Integer -> Either MathError Integer Source #

Floor of the square root, computed by exact integer Newton iteration.

perfectPower

perfectPower :: Integer -> Maybe (Integer, Int) Source #

Find a representation n = base^exponent with exponent greater than one. Zero, one, and minus one use exponent 2, 2, and 3 respectively.

isPrimeExact

isPrimeExact :: Int -> Integer -> Either MathError Bool Source #

Proven primality using trial division. The budget counts trial divisors.

nextPrime

nextPrime :: Int -> Integer -> Either MathError Integer Source #

First proven prime at least the requested integer. The budget bounds both candidate count and trial divisions per candidate.

millerRabin

millerRabin :: [Integer] -> Integer -> Either MathError Bool Source #

Strong Miller--Rabin for explicitly supplied bases (each >=2). Passing is probable primality, not a proof. No random-base probability bound is claimed for caller-selected deterministic bases. An empty base list is rejected.

bailliePSW

bailliePSW :: Integer -> Either MathError Bool Source #

Baillie--PSW: base-2 strong Miller--Rabin plus strong Lucas--Selfridge. Perfect squares are rejected. Passing is probable primality for arbitrary integers; no unproved claim of deterministic primality is made. Selfridge parameter search is limited to 10000 discriminants.

sieveEratosthenes

sieveEratosthenes :: Int -> [Integer] Source #

Eratosthenes sieve through an inclusive nonnegative upper bound.

sieveAtkin

sieveAtkin :: Int -> [Integer] Source #

Atkin quadratic-residue sieve, followed by removal of prime-square multiples.

segmentedSieve

segmentedSieve :: Integer -> Integer -> Either MathError [Integer] Source #

Segmented sieve on the inclusive interval [lo,hi]. The segment width and the square-root base sieve must fit an Int; reversed intervals are rejected.

primeFactorization

primeFactorization :: Int -> Integer -> Either MathError [(Integer, Int)] Source #

Exact trial factorization of a positive integer. The budget counts attempted divisors (including repeated factors). One has an empty factorization.

pollardRho

pollardRho :: Int -> Integer -> Integer -> Either MathError Integer Source #

Pollard rho with Floyd cycle detection, explicit seed and iteration budget. Returns a proper divisor or failure; a failed seed does not prove primality.

pollardPMinusOne

pollardPMinusOne :: Int -> Integer -> Integer -> Either MathError Integer Source #

Pollard p-1 stage one with a smoothness bound >=2 and base. The exponent includes the maximal powers of every prime <= the bound.

fermatFactor

fermatFactor :: Int -> Integer -> Either MathError Integer Source #

Fermat difference-of-squares factorization, with an explicit step budget.

divisors

divisors :: Int -> Integer -> Either MathError [Integer] Source #

All positive divisors in increasing order, under a factorization budget.

divisorSum

divisorSum :: Int -> Integer -> Either MathError Integer Source #

Sum of positive divisors.

divisorCount

divisorCount :: Int -> Integer -> Either MathError Integer Source #

Number of positive divisors.

eulerTotient

eulerTotient :: Int -> Integer -> Either MathError Integer Source #

Euler totient, including phi(1)=1.

carmichael

carmichael :: Int -> Integer -> Either MathError Integer Source #

Carmichael's exponent of the multiplicative unit group.

mobius

mobius :: Int -> Integer -> Either MathError Integer Source #

Mobius function on positive integers.

liouville

liouville :: Int -> Integer -> Either MathError Integer Source #

Liouville function, counting prime factors with multiplicity.

multiplicativeOrder

multiplicativeOrder :: Int -> Integer -> Integer -> Either MathError Integer Source #

Multiplicative order of a unit modulo a modulus >1.

primitiveRoot

primitiveRoot :: Int -> Integer -> Either MathError Integer Source #

Smallest generator of the units modulo m, if that group is cyclic. Search and factorization are both bounded; noncyclic groups report a domain error.

discreteLog

discreteLog :: Int -> Integer -> Integer -> Integer -> Either MathError Integer Source #

Baby-step giant-step discrete logarithm of a unit. Budget bounds the table dimension, so storage is O(budget) and work O(budget*log budget), apart from integer arithmetic. The smallest nonnegative exponent is returned.

legendreSymbol

legendreSymbol :: Int -> Integer -> Integer -> Either MathError Integer Source #

Legendre symbol for a proven odd prime modulus, with proof budget.

jacobiSymbol

jacobiSymbol :: Integer -> Integer -> Either MathError Integer Source #

Jacobi symbol for a positive odd denominator.

kroneckerSymbol

kroneckerSymbol :: Integer -> Integer -> Integer Source #

Kronecker symbol, extending Jacobi to every integer denominator.

tonelliShanks

tonelliShanks :: Int -> Integer -> Integer -> Either MathError Integer Source #

Tonelli--Shanks modular square root for a proven prime modulus. Returns the smaller of the two roots; a nonresidue is a domain error. Proof and nonresidue search each respect the supplied budget.